이진 탐색 (Binary Search)

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

처음 선택한 중앙값이 만약 찾는 값보다 크면, 그 값은 새로운 최대값이 되며, 작으면 그 값은 새로운 최소값이 된다.

단점

검색 원리상 정렬된 리스트에만 사용할 수 있다

장점

검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.

시간복잡도

O(logN)

공간복잡도

O(1)

코드

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (target == arr[mid]) {
            return mid;
        }else if (arr[mid] < target) {
            start = mid + 1;
        }else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target.");
}

출처