[CS] 이분 탐색 (JAVA)

이분 탐색이란

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 원하는 데이터를 탐색하는 방법이다.
리스트의 중간 부분에 찾는 데이터가 있는지 확인하고, 없으면 왼쪽에 있는지 오른쪽에 있는지 판단한다.
이분 탐색은 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.

 

이분 탐색의 시간복잡도

원하는 데이터를 찾을 때까지 처음부터 끝까지 계속 탐색하는 순차 탐색은 Worst Case일 때 \(O(N)\) 이라는 시간복잡도를 가지므로 10만개의 데이터가 있을 때 10만번을 탐색해야 한다.

그러나, 이분 탐색은 탐색 대상을 절반씩 계속해서 줄여나가기 때문에 Worst Case일 때에도 탐색의 횟수가 \( log_{2} N \)이 되어 \(O(log N)\) 의 시간복잡도를 가지므로 10만개의 데이터가 있더라도 17번 이내로 탐색을 끝낼 수 있다.

 

이분 탐색의 구현

int binarySearch(int[] array, int target) {
    int start = 0;
    int end = array.length - 1;
    int mid = (start + end) / 2;

    while (start <= end) {
        if (array[mid] == target) {
            // 원하는 데이터를 찾음
            return mid;
        }
        else if (array[mid] < target) {
            // 원하는 데이터가 array[mid] 우측에 위치함
            start = mid + 1;
        }
        else {
            // 원하는 데이터가 array[mid] 좌측에 위치함
            end = mid - 1;
        }
       
        mid = (start + end) / 2;
    }
    
    // 원하는 데이터가 array 배열 안에 없음
    return -1;
}