이진 탐색(Binary Search)

배열이 정렬되어 있을 때, 가운데 값과 비교하여 찾고자하는 값이 더 크면 오른쪽을 작다면 왼쪽을 탐색하는 방식

 

예시

[2, 5, 7, 9, 14, 19, 20, 24]가 있을 때 만약 2를 찾고 싶다면

가운데 값인 14와 비교를 하면 더 작기 때문에 다시 왼쪽 부분인 [2, 5, 7, 9]에서 같은 방식으로 반복한다.

최종적으로 2를 찾아 인덱스를 리턴하게 된다.

 

장점

시간복잡도가 log n으로 상당히 빠르다.

완전 탐색을 수행했을 때 시간 초과가 나는 여러 문제에서 활용될 수 있다.

 

 

구현

재귀로 구현

int recursive_binarySearch(vector<int> arr, int start, int end, int target){
    if(start > end) return -1;

    int mid = (start + end) / 2;
    if(arr[mid] == target) return mid;
    else if(arr[mid] > target){
        return recursive_binarySearch(arr, start, mid - 1, target);
    }
    else return recursive_binarySearch(arr, mid + 1, end, target);
}

 

반복문으로 구현

int while_binarySearch(vector<int> arr, int start, int end, int target){
    while(start <= end) {
        int mid = (start + end) / 2;
        if(arr[mid] == target) return mid;
        else if(arr[mid] > target) end = mid - 1;
        else start = mid + 1;
    }
}