[Algorithm] Binary Search (이진 탐색)

0. Binary Search (이진 탐색) 이란?

 

업-다운 게임을 생각해보자 (술을 많이 안 먹으면 모를 수도 있다..이 경우엔 검색해보자).

범위 내에서 특정 숫자를 말하면 업, 다운을 이야기하며 맞추면 당연히 모두 읊는 것보다 시간이 덜 소요될 것이다.

이진 탐색과 이 개념은 정확히 일치한다.

 

배열이 정렬되었다고 가정하자. 이진 탐색은 정렬된 배열에 대해서만 가능하다.

정렬된 배열의 가운데에서 업, 다운 중 하나를 선택하면 왼쪽 혹은 오른쪽으로 이동할 것이다.

이제 이동한 배열의 가운데를 다시 기준으로 업, 다운을 선택하면, 범위가 계속 좁아지며 결국 원하는 대상을 찾을 수 있을 것이다.

만약 원하는 대상이 없다면, 배열의 원소가 하나만 남았을 때도 원하는 대상이 아닐 것이고, 이 때는 찾을 수 없다고 종료하면 된다.

 

이를 좀 더 프로그래밍적으로 이야기하면, 정렬된 배열의 가운데를 mid로 잡아 타겟보다 크면 왼쪽, 타겟보다 작으면 오른쪽으로 이동한다.

이후 왼쪽으로 이동했을 경우 mid-1을 오른쪽 끝으로, 오른쪽으로 이동했을 경우 mid+1을 왼쪽 끝으로 삼고 다시 가운데를 mid로 잡는다.

이 과정을 원하는 원소가 나타날 때까지 반복한다.

 

예를 들어보면, [23, 34, 36, 41, 45, 49, 52, 57]에서 49를 찾는다고 하자. 첫 mid는 8/2인 4번째, 즉 3번 원소가 될 것이다.

3번 원소는 49보다 작으므로 오른쪽으로 이동한다. 이제 41부터 57까지가 새로운 범위가 된다.

여기서 다시 mid를 잡으면 (4+7)/2=5, 즉 49가 mid가 된다. 찾았으니 종료한다.

 

만약 위와 같은 배열에서 48을 찾는다고 가정해보자. 41부터 57까지가 새로운 범위가 되는 것은 같을 것이다. 새로운 mid인 49가 48보다 크므로 새로운 범위는 41부터 45까지가 되고, mid는 41이 된다. 41이 48보다 작으므로 오른쪽으로 이동한다. 오른쪽으로 이동하면 원소가 하나 남는데, 이 때도 타겟을 찾을 수 없으므로 -1 (찾을 수 없음) 을 반환한다. 

 

1. 구현 

 

n_m = input()
a = n_m.split()
n = (int)(a[0])
m = (int)(a[1])

nums = input()
num = nums.split()

for i in range(n):
    num[i] = (int)(num[i])

targets = []
for i in range(m):
    targets.append(int(input()))

res = []

def binary_search(num, target):
    n = len(num)

    for i in range(m):
        left = 0
        right = n - 1

        while left <= right:
            mid = (int)((left + right) / 2)
            if target is num[mid]:
                return mid + 1
            else:
                if target < num[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

        return -1

for i in range(m):
    res.append(binary_search(num, targets[i]))

for j in range(m):
    print(res[j])

문제는 codetree의 숫자 빠르게 찾기 문제이다 (https://www.codetree.ai/missions/6/concepts/31/problems/find-number-fast/description).

코드트리

n개의 숫자가-1 오름차순으로 정렬된 상태로 주어지고, m개의 찾고자 하는 숫자가 주어진다. m개의 각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번째로 나온 숫자인지를 구하는 코드를 작성했다. 찾을 수 없다면 -1을 반환한다.

 

정렬과는 다르게, 원소가 마지막 하나만 남아있을 때도 판단이 가능하므로 조건을 left <= right로 설정한다. mid를 잡고, mid보다 찾고자 하는 수가 크면 오른쪽으로 이동 (mid+1~right를 새로운 범위로 함), 작으면 왼쪽으로 이동 (left~mid-1을 범위로 함) 을 찾을 때까지 반복한다. 만약 원소가 하나만 남으면 (left==right 혹은 left>right) 이면 -1을 반환한다.