이진 검색 알고리즘

이진 검색이란 무엇입니까?
이진 검색은 대수 실행 시간 복잡도에서 정렬된 배열의 요소를 찾는 데 사용되는 검색 알고리즘 중 하나입니다.

참고: 이진 검색은 정렬된 배열에만 적용할 수 있습니다.

이진 검색이 선형 검색보다 나은 이유
이진 탐색은 O(log(n)) 대수 시간 복잡도를 가지며 선형 탐색은 O(n) 선형 시간 복잡도를 갖습니다.

이진 검색 작동 방식
이진 검색은 주어진 배열에서 요소를 검색하기 위해 분할 정복 전략을 사용합니다. 이진 검색은 검색 영역을 각 패스에서 정확히 절반으로 나눕니다.

start : 시작 인덱스의 값을 저장
end : 종료 인덱스 값을 저장
mid : 중간 인덱스 값을 저장

시작 = 0
끝 = array_length -1
mid = (start + end)/2//하지만 좋은 습관은 아닙니다.
(start + end)는 때때로 정수 제한을 초과할 수 있습니다.

mid = start + (end - start)/2//이것이 올바른 방법입니다.

처음에 배열 nums = { 1, 2, 4, 8, 10, 50, 70, 88, 100 }이 있고 대상 요소가 70이라고 가정합니다.
먼저 배열의 중간 요소가 대상과 같은지 확인합니다. 같으면 중간 인덱스 또는 중간을 반환합니다. 그렇지 않은 경우 대상이 중간 요소보다 작거나 큰지 확인하십시오.
대상이 작으면 중간 요소가 검색 공간을 줄입니다. end = mid -1입니다. 이제 새 검색 공간은 (시작, 중간 -1)입니다.
target이 더 크면 중간 요소가 검색 공간을 줄입니다. start = mid +1입니다. 이제 새 검색 공간은 (mid+1, end)입니다.

따라서 각 패스에서 검색 공간은 시작 <= 끝이 될 때까지 절반으로 줄어듭니다. 시작이 끝보다 커지면 루프가 중단됩니다.

연산
Java의 이진 검색

import java.util.Arrays;  

public class BinarySearch {
    public static void main(String[] args) {

        int[] nums = { 1, 2, 3, 19, 29, 40, 60, 100 };
        int target = 40;

        System.out.println(Arrays.toString(nums));
        System.out.println(binarySearch(nums, target));
    }

    static int binarySearch(int[] nums, int target) {

        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {

            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }

        }

        return -1;
    }
}