이분 탐색(Binary Search)

이분 탐색이란 이름 그대로 두 개로 나누어 탐색을 한다는 것이다.

기본적인 구조는 분할정복과 유사하지만, 반을 나누고 둘 중 한쪽으로만 탐색을 진행한다는 점에서 차이가 있다.

 

그럼 이분탐색은 어떻게 진행하는지 알아보자.

 

이분 탐색의 가장 대표적인 예로 Up, Down 게임이 있다.

Up, Down 게임은 상대방이 어떤 숫자를 생각하면, 도전자가 숫자를 예측하며,

상대방은 그 숫자에 대해 Up, Down을 말한다.

 

그럼 이 방법에서 최소한의 횟수로 정답을 맞추는 방법은 뭘까

바로 내가 말할 수 있는 숫자의 범위 중, 정확히 반에 해당하는 숫자를 말하는 것이다.

 

게임을 통해 예시를 들어보자.

나무위키에서 가지고 왔다

해당 게임에서는 상대방이 77이라는 숫자를 생각하였고, 우리는 그 숫자를 맞추기 위해 숫자를 부를 것이다.

 

일단 우리가 부를 수 있는 숫자의 범위는 1부터 100 사이 이기 때문에 우리는 50을 불러준다.

그러면 상대방은 Up 이라고 대답할 것이고, 우리가 부를 수 있는 범위는 51부터 100 사이가 된다.

(설마 Up 을 불렀는데 50보다 낮은 숫자를 말하겠는가)

 

그러면 우리는 위와 같은 과정을 반복해 준다.

51에서 100 사이에서 중간 값은 75 또는 76이 된다. ( 둘 중에 하나를 골라주면 된다.)

여기서는 75를 골라주겠다.

 

75를 말했을 때, 다시 한번 Up이라는 대답이 돌아온다. 

그러면 다시 범위를 줄여서 반복해 주면 된다.

그러면 총 7번의 횟수로 상대방이 생각한 숫자 77을 찾을 수 있게 된다.

 

이때 찍어서 맞추면 7보다 적은 횟수를 맞출 수 있지 않냐라고 말할 수 있지만, 알고리즘 문제를 풀 때 확률에 의존해서 문제를 푸는 건 좋지 않다.

물론 랜덤을 써서 푸는 문제도 존재한다.

하지만 그 수가 적기에 웬만하면 대부분의 케이스에서 특정 시간복잡도를 만족하는 풀이가 좋다.

 

그렇기에 랜덤 한 위치를 나누는 것이 아닌 정확히 절반을 나누는 과정을 통해 값을 찾는다.

구간의 절반을 나누게 된다면, 최대 시간복잡도 O(logN) 이 나오게 된다.

 

여기서 N은 선택할 수 있는 전체 숫자의 개수이고, logN는 log 2의 k 승이 N 임을 의미한다.

(알고리즘 쪽에서는 logN을 밑을 10으로 두는 것이 아닌 2로 둔다.)

 

log를 배웠다면 알 수 있지만, 모든 과정에서 절반씩 나누기 때문에 2^k >= N을 만족하는 k 가 최대 시도 횟수가 된다.

 

코드로 작성하면 이렇게 나온다.

ans=77
def func(start,end,i):
    mid=(start+end)//2
    print(f"{i}번째 추측 : {mid}")
    if mid<ans:
        func(mid+1,end,i+1)
    elif mid>ans:
        func(start,mid-1,i+1)
    else:
        print("find answer")
        return

func(1,100,1)

 

실행해 봤을 때 7번 안에 답을 찾는 것을 알 수 있다.

 

이런 이분탐색을 이용한 방법에는 여러 가지가 있는데 그중 가장 대표적으로 파라메트릭 서치가 있다.

파라메트릭 서치란 문제 상황을 만족하는 최솟값 혹은 최댓값을 구하는 문제에 활용된다.

 

이때에는 위와 같이 조건에 따라 중간점 기준 왼쪽 구간으로 탐색을 할지, 오른쪽 구간으로 탐색으로 탐색을 할지 고르는

 

조건문에서 무조건 아닌 것은 제외하는 방법을 사용하여 진행한다.

 

무조건 아닌 것은 제외한다는 말은 중간점의 조건 만족 여부에 따라 중간점을 포함하거나 혹은 중 감점을 포함하지 않고 위 코드처럼 왼쪽/ 오른쪽 구간을 탐색하는 것을 말한다.

 

이런 경우 탐색하는 구간의 입력이 들어오는데 이때 해당 입력을 정렬할 수 있을 때, 이분탐색(파라메트릭 서치)을 이용할 수 있다.

 

1부터 100 사이의 숫자를 찾는 것도 1부터 100까지의 숫자가 정렬되어 있기 때문에 가능한 것이며, 이분탐색의 대전제는 탐색하려는 구간이 정렬이 되어있다가 된다.