[도구정리] Binary Search(이분탐색/이진탐색)

개념

이진탐색은 정렬된 배열에서만 사용 가능한 탐색법이다.

변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방식이다.

 

O(logN)의 시간 복잡도를 가진다. (컴퓨터이기에 log는 log₂이다.)
단계마다 탐색 범위를 절반으로 나누어가며 진행하기 때문이다.
예를 들어, 처음 데이터의 개수가 32개라면,

1단계를 거치면 약 16개의 데이터가 남고,

2단계에서 약 8개,

3단계에서 약 4개의 값을 탐색하게 된다.
즉, 이진 탐색(이분 탐색)은 탐색 범위를 절반씩 줄여가며, O(logN)의 시간 복잡도를 보장한다.

---

구현(JAVA)

  public static int binarySearch(int num){
        // 1 2 4 가 있는데 3이 들어옴
        int start = 0; // 0
        int end = list.size()-1; // 2
        int mid = (start + end) / 2; // 1
        while(start <= end){
            mid = (start + end) / 2;
            if(list.get(mid) == num){ // 처음에 mid == 1이기 때문에 3이 아님 (list.get(mid) == 2)
                return mid;
            }
            if(list.get(mid) < num){ // 처음에 mid == 1이기 때문에 3보다 작음 (list.get(mid) == 2)
                start = mid + 1; // start = 1 + 1이므로 2이가 됨.
                continue;
            }
            end = mid - 1; // start = 2가 되었을 때 mid = 2가 되고, list.get(mid) == 4이므로 여기로 내려옴.
            // end = 2 - 1이 되어 반복문 끝남.
        }
        return start; // 2가 반환됨
    }

 

최종적으로 반환되는 int값은 인덱스 값이다.

이 코드의 목표는 자기 자신보다 큰 수 중 최소의 값을 찾는 것이다.

 

주석으로 기술되어 있는 코드의 흐름을 다시 살펴보자.

 

1

2

4

현재 리스트에는 1, 2, 4가 들어있다고 하자. 문제에 따라 정렬을 하고 이분탐색을 진행하거나, 정렬이 되어있는 배열에 진행하면 된다.

중요한 것은 정렬이 꼭 되어있어야 한다는 것이다.

 

start = 0, end = list.size() - 1(여기서는 2), mid = 1로 시작한다.

반복문은 start <= end일 때까지 진행하며, 문제와 상황에 따라 등호가 필요하거나 필요하지 않을 수도 있다. 그렇기에 코드의 동작 과정을 정확히 이해하자.

 

1. 시작하면 mid 값을 조정한다.

2. list.get(mid) == num이라면 정확한 값을 찾은 것이기 때문에 바로 리턴한다. (여기서는 list.get(mid)가 2이기 때문에 만족하지 못한다.

3. list.get(mid) < num이라면 start = mid + 1로 해준다. 정렬이 보장되어 있는 상태에서 mid가 타깃값보다 작다면 mid 이하는 전부 필요 없다는 소리이다. start를 mid +1로 인덱스를 조정해 주자.

4. list.get(mid) > num이라면 end = mid - 1로 해준다. 정렬이 보장되어 있는 상태에서 mid가 타깃값보다 크다면 mid 이상은 전부 필요 없다는 소리이다. end를 mid - 1로 인덱스를 조정해 주자.

 

결과적으로 반복문이 끝날 때까지 절반의 탐색을 이어가며 목푯값을 찾는 과정이 완성된다.

 

Binary Search는 정렬이 보장된 배열(리스트)에서 값을 찾는데 유용하다!