Binary Search - 간단 정리

모든 것은 배열이나 리스트가 정렬되어 있다는 가정하에 진행한다. 이진 탐색은 거의 다음과 같은 형태로 정형화 가능하다.

private static void binarySearch(ArrayList<T> arr, T target) {
    int min = 0;
    int max = arr.size()-1;
    int mid;
    
    while(mid ~ max) {
        mid = (min + max) / 2;
        
        if(?)
        if(arr.get(mid) ~ target)
        else
    
    return k;

보통 ~에 비교 관계가 어떻게 들어가냐에 따라 다르다. while 문을 먼저 살펴보자.

 

공식

// 1.
while(min < max)

// 2.
while(min <= max)

1번의 형태는 min과 max가 정확히 일치할 때까지 지속한다. 이와 반대로 2번은 min과 max가 1차이가 나게 된다. 이는 마지막 값이 어떻냐에따라 min이 +1되거나 max가 -1이 된다. 보통 1번을 많이 쓴다.

 

// 1.
if(arr.get(mid) <= target) min = mid+1;
else max = mid-1;

// 2.
if(arr.get(mid) < target) min = mid+1;
else max = mid-1;

 두번째 조건문에서는 등호가 있냐 없냐인데, 여기서 1번의 경우 값이 같은게 연속으로 나왔을때, 연속적인 그 수들의 가장 오른쪽에 초점을 맞춘다. 즉, min이 이동한다. 하지만 2번의 경우 max가 이동하게 된다. 이를 통해 연속적인 값들의 가장 왼쪽의 index 혹은 가장 오른쪽의 index를 반환 할 건지 결정할 수 있다.

 

변형

보통 원소 혹은 어떤 객체들의 집합의 원소들과 관계가 있는 어떤 객체를 찾으라는 문제로 나올 것이다. 그런 조건들을 찾아서 첫번째 조건문에 추가할지, 아니면 두번째 조건문에 추가할지 아니면 새로운 조건을 또 만들지를 결정하여 상황에 맞게 코딩을 하는 것이 좋다.