Binary Search
이 사람을 찾는게 아니다!!!
정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.
보통 대학교 1학년 프로그래밍 교재에 간단한 예제와 함께 소개되어 있는 경우도 있고, 분할과 정복의 쉬운 예제로 정렬된 배열에서 이진탐색을 해서, 분할과 정복의 원리를 깨우쳐 주는 교수도 있다. 이것의 원리는 간단한 것으로 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하는 걸 생각하면 쉽다.
즉,
function 이진탐색(데이터, 찾는 값) 데이터가 혹시 비어 있는가? (네) return 찾는 값 없음. 데이터의 가운데 지점을 찾는다. 찾은 지점의 데이터를 뽑는다. 뽑은 데이터가 찾는 값인가? (네) return 뽑은 데이터. (아니오) 뽑은 데이터와 찾는 값을 비교한다. (뽑은 데이터가 찾는 값보다 큰 값인가?) return 이진탐색(데이터 앞쪽 절반, 찾는 값) (작은 값인가?) return 이진탐색(데이터 뒤쪽 절반, 찾는 값)
// 재귀적 이진 탐색의 C언어 예제 코드 int bSearch(T arr[], T val, int first, int last) { if (first >= last) return -1; int mid = (first + last) / 2; if (val == arr[mid]) return mid;
else if (val
# 비재귀적 이진탐색의 Python 코드 def BinarySearch (arr, val): first, last = 0, arr.len() while first val: last = mid else: first = mid return -1
이렇게 된다[1]. 혹시 의사 코드를 못 읽는 사람을 위해 서술식으로 설명해보자면 주어진 리스트의 가운데 지점의 값을 비교해보고 그게 찾는 값보다 크면 뒤쪽 반을 잘라 버리고 작으면 앞쪽 절반을 잘라버린 다음에 그 '잘린' 리스트를 대상으로 똑같은 짓을 또 하는 것이다. 이게 원하는 값을 찾든지 아니면 다 버려버리든지(찾는 값 없음) 할 때까지 반복한다.
맞다. 이것은 재귀함수이다. 대부분의 이진 탐색은 비재귀로 구현되지만 그 본질은 이 재귀판 함수와 같다.
이진 탐색은 처음부터 끝까지 순서대로 찾는 순차 탐색에 비해 굉장히 빠르지만[2], 사전을 든 예시에서 볼 수 있듯이 미리 정렬이 되어 있어야 되는 점, 경우에 따라서는 쓰기 곤란한 경우도 있다는 점이 단점이다. 이를테면 연결 리스트같은 것에 이진 탐색을 쓰기 곤란하다. 연결 리스트는 테이프같은 구조라 무작위 위치로 점프하질 못하고 앞뒤로 움직이기만 가능하기 때문이다. 물론 약간의 트릭을 쓰면 연결 리스트에서 이진 탐색이 가능하다.
O(logn) 의 위력이 감이 잘 안온다면, 4,294,967,296개(약 43억개)의 원소가 있는 리스트에서 원하는 특정 값을 찾아낼 때 최악의 탐색 깊이(찾는 값이 없는 경우)는 딱 32회이다. 그러나 순차 탐색의 최악의 경우는 4,294,967,296회이다. 저게 0부터 순서대로 숫자가 들어있는 리스트라고 할 때 순차 탐색이 이진 탐색보다 빠른 지점은 32까지. 33부터 그 나머지 구간에서는 이진 탐색이 순차 탐색보다 빠르다. 33회의 비교시에는 약 86억개의 자료를 탐색할 수 있다. 우주에 존재하는 모든 원자 개수만큼의 원소를 가지는 리스트를 주어줘도 약 120회 정도만 비교하면 원하는 값을 찾을 수 있다.
'뭐 하러 무식하게 일일이 비교하고 있나, 32를 찾고 싶으면 그냥 리스트의 32번째 원소를 읽으면 되지' 하고 생각하는 분은, 저게 그냥 예시라는 사실을 기억해주기 바란다. 어떤 데이터가 들어가 있는지 모르는 리스트에서 하나 알고 있는 건 그 리스트가 정렬돼 있다는 것뿐이다. 만약 어떤 데이터가 어떤 방식으로 들어가 있는지도 알고 있다면 이것보다 더 빠른 해시 탐색을 사용할 수 있다. 해시 탐색의 시간복잡도는 O(1)이다. 말 그대로 리스트의 길이에 영향을 받지 않고 항상 일정한(상수)시간안에 찾아낸다.