이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 정렬된 배열이나 리스트에서 중앙 값과 찾고자 하는 값을 비교해가며 탐색 범위를 절반씩 줄여나갑니다.

시간 복잡도

배열이나 리스트를 처음부터 하나씩 탐색하는 방법을 선형 탐색이라고 합니다. 선형탐색의 시간복잡도는 원소 개수와 비례하여 O(N)의 시간 복잡도를 갖습니다.

이진 탐색은 한번 검사할 때마다 탐색 범위를 절반씩 줄여나가므로 처음 탐색 범위의 크기가 N이라고 한다면 한번 검사한 후에는 N/2, 두번 검사한 후에는 N/4, 세번 검사한 후에는 N/8입니다. 따라서 x번 검사한 후에는 탐색 범위의 크기는 N/2^x입니다.

최악의 시간 복잡도를 구한다 치면, 이진 탐색으로 최대 몇번의 검사를 할 수 있는지 생각해봅니다. 탐색 범위가 마지막 하나의 원소가 남을때까지 검사가 실행된다고 한다면 N/2^x = 1이 됩니다. 따라서 최대 탐색 횟수 x = logN이 됩니다. 이진 탐색의 시간 복잡도는 O(logN)이 됩니다.

코드로 보는 이진 탐색

• 숫자 배열에서 이진 탐색

private static boolean binarySearch(int[] arr, int x){
        // 탐색 범위 초기화(전체)
        int start_index = 0;
        int end_index = arr.length - 1;

        // 탐색 범위를 절반씩 줄여나가며 중앙값과 비교해본다.
        while(start_index <= end_index){
        	// 배열의 중앙값을 구한다.
            int mid_index = (start_index + end_index) / 2;
            int mid_value = arr[mid_index];

  			// 중앙값과 찾고자하는값 x와 비교한다.
            if(mid_value < x){
            	// 중앙값이 찾고자하는값보다 작을 때
                start_index = mid_index + 1;
            }else if(mid_value > x){
            	// 중앙값이 찾고자하는값보다 클 때
                end_index = mid_index - 1;
            }else{
            	// 중앙값이 찾고자하는값과 일치할 때
                return true;
            }
        }
        return false
 }

• 문자열 배열에서 이진 탐색

private static boolean binarySearch(String[] arr, String x){
        // 탐색 범위 초기화(전체)
        int l = 0, r = arr.length - 1;
        
        while(l <= r ){
            int m = (l + r) / 2;
            
            // 양수: x보다 사전순서로 뒤에 있다. 음수: x보다 사전순서로 앞에 있다.
            int compareResult = arr[m].compareTo(x);
            
            if(compareResult < 0){
                l = m+1;
            }else if(compareResult > 0){
                r = m-1;
            }else{
                return true;
            }
        }
        return false;
 }

자바의 이진 탐색 메서드

배열과 리스트에 적용할 수 있는 자바 내장 메서드가 있습니다.
주의해야할 점은 배열과 리스트는 정렬된 상태여야 합니다.

자료구조	메서드
배열	Arrays.binarySearch(array, x)
리스트	Collections.binarySearch(list, x)

위의 두 메서드는 찾고자하는 값 x가 있다면 해당 원소의 인덱스를 반환합니다. 일치하는 원소가 여러 개 있다면 무작위의 인덱스를 반환합니다.

만약 없다면 음수가 반환되는데, 이 값을 이용하면 x가 배열이나 리스트에서 어느 위치에 들어가야하는지 예측할 수 있습니다.

int[] array = new int[] {1,2,3,5,6,7};
List<Integer> list = List.of(1,2,3,5,6,7);

int arrayIndex = Arrays.binarySearch(array, 4); // -4
int listIndex = Collections.binarySearch(list,4); //-4

여기서 반환값 -4는 해당 배열과 리스트에 찾고자하는 값 4가 존재하지 않는다는 의미와 만약에 4가 들어가야한다면 해당 변환값을 양수로 바꾼 후 1을 뺀 3번째 인덱스 위치에 들어가야한다는 의미도 포함됩니다.