이분 탐색 : Binary Search

이분 탐색에 대해 논해보자. 둘로 나눠서 검색을 시도하는 이 내용은 n고개 게임에서 쉽게 찾을 수 있다.

생각하는 숫자를 n고개 안에 맞추는 게임은 숫자를 제시하면 업, 다운을 제시해서 범위를 줄여나간다.
일정한 범위 내에서 상대가 숫자를 정했을 때 나는 그 범위의 절반을 딱 잡아서 부른다. 그리고 업 다운에 따라 검색 범위를 좁혀 나간다.
이렇게 장황하게 써보니 떠오른게 이분 탐색은 정렬이 기본 전제 되어 있어야한다. 정렬이 되어있지 않으면 내가 특정한 위치를 찍어서 더 크다, 작다를 논 할 수 없기 때문이다.

그리고 이분 탐색은 범위를 반으로 나누고 그대로 함수에 매개변수로 넣어 타고 들어간다는 점에서 합병 정렬과 약간 유사한 면이 있다.

더 요약해서, 이분 탐색은 탐색 중 나오는 결과에 기반해 검색 범위를 줄여나가면서 검색을 시도하는 기법이다. 이 기법은 시간 복잡도가 꽤 훌륭한 편에 속하며 재귀 함수를 주로 이용하여 구현되곤 한다.

만약 내가 1부터 10까지 주어진 상황에서, 7을 찾겠다고 해보자.

1

2

3

4

5

6

7

8

9

10

이 상황에서 일반적으로는 str + end에 2를 나눠서 가운데인 5 (또는 6)을 찍는다. 나는 설명 상 편의를 위해 5가 [mid]라고 하겠다.
당연하게도 [mid]는 내가 찾는 7이 아니다.
근데 이 비교과정에서 [mid]가 기존에 찾는 값보다 크냐 작냐를 통해 다음 범위를 결정 할 수 있다는게 이분 탐색의 핀트이다.

어쨌든 [mid]의 값인 5까지는 답이 아닌거다.
그럼 [mid + 1]은 새로운 str이 되어 또 탐색을 수행한다. 앞에서 설명한 것에 기반하면 [mid + 1]은 6에서 시작한다.

6

7

8

9

10

여기서의 [mid]는 8이다. 이번에는 결과보다 큰 상황이다. 따라서 end를 조정 해야 한다.
end는 mid - 1이 되어 새로운 호출을 하게 된다. 당연하게도 이 상황에서는 str은 유지된다.

6

7

이걸 반복하면 7을 찾을 수 있다. 후반부는 넘기겠다.

psudo of binary search

function(arr, findTarget, str, end)
	if(str이 end를 넘어간 경우)
    	return -1
        # 이런류를 명시적으로 처리하는건 무척 중요하다.
	
    if(str와 end의 차이가 한 칸만 가리키는 경우)
        if(해당 하는 칸의 내용이 findTarget이랑 다르면)
            return -1
    mid = (str + end) / 2

    if arr[mid] == findTarget
        done!
        return mid
else if arr[mid] > findTarget
       return function(arr, findTarget, str, mid - 1)
        # return을 앞에 잊지 말기
        # 탐색 범위에 대해 축소를 end를 수정함으로써 이루어진다.
else if arr[mid] < findTarget
       return function(arr, findTarget, mid - 1, end)
        # 탐색 범위에 대해 축소를 str을 수정함으로써 이루어진다.

내 의사 코드