1. 개요
Binary Search정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.
이진 탐색 알고리즘(二進探索algorithm, Binary Search Algorithm)은 컴퓨터과학, 수학 등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.[1]
2. 상세
이진 탐색의 개념은 보통 대학교 1학년 프로그래밍 교재에 간단한 예제와 함께 소개되어 있는 경우도 있고, 분할과 정복의 쉬운 예제로 나오기도 한다. 이 알고리즘의 원리는 간단한 것으로 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하는 걸 생각하면 쉽다. 단, 이진 탐색을 위해서는 자료가 순서에 따라 정렬되어 있어야 한다. 다음 그림은 이진 탐색으로 원하는 숫자 77을 찾는 과정이다.술자리에서의 up/down 게임의 효율적 전략과 완벽히 일치한다.
먼저, 50부터 탐색을 시작한다. 77은 50보다 크므로 왼쪽 포인터를 오른쪽으로 이동한다. 그다음은 75다. 77은 75보다 크므로 마찬가지로 왼쪽 포인터를 오른쪽으로 이동한다. 다음은 87이다. 77은 87보다는 작으므로 이번에는 오른쪽 포인터를 왼쪽으로 이동한다. 이런 식으로 점점 범위를 좁혀 나가면 7번 이내에 무조건 숫자를 맞출 수 있게 된다. 마찬가지로 이 그림에서도 7번의 비교로 정답을 찾아냈다.
즉,
function 이진탐색(데이터, 찾는 값)
데이터가 혹시 비어 있는가?
(네) return 찾는 값 없음.
데이터의 가운데 지점을 찾는다.
찾은 지점의 값을 뽑는다.
뽑은 값이 찾는 값인가?
(네) return 뽑은 값.
(아니요)
뽑은 값과 찾는 값을 비교한다.
(뽑은 값이 찾는 값보다 큰 값인가?)
return 이진탐색(데이터 앞쪽 절반, 찾는 값)
(작은 값인가?)
return 이진탐색(데이터 뒤쪽 절반, 찾는 값)
#!syntax cpp
// 재귀적 이진 탐색의 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 < arr[mid])
return bSearch(arr, val, first, mid - 1);
else
return bSearch(arr, val, mid + 1, last);
}
#!syntax python
# 비재귀적 이진탐색의 Python 코드
def binary_search (arr, val):
first, last = 0, len(arr) - 1
while first <= last:
mid = (first + last) // 2
if arr[mid] == val:
return mid
if arr[mid] > val:
last = mid - 1
else:
first = mid + 1
return -1
이렇게 된다[2]. 혹시 의사 코드를 못 읽는 사람을 위해 서술식으로 설명해보자면 주어진 리스트의 가운데 지점의 값을 비교해보고 그게 찾는 값보다 크면 뒤쪽 반을 잘라 버리고 작으면 앞쪽 절반을 잘라버린 다음에 그 '잘린' 리스트를 대상으로 똑같은 짓을 또 하는 것이다. 이게 원하는 값을 찾든지 아니면 다 버려버리든지(찾는 값 없음) 할 때까지 반복한다.
상기 코드들은 재귀함수로 구현되어 있다. 대부분의 이진 탐색은 비재귀로 구현되지만 그 본질은 이 재귀판 함수와 같다.
이진 탐색은 처음부터 끝까지 순서대로 찾는 순차 탐색에 비해 굉장히 빠르지만[3], 사전을 든 예시에서 볼 수 있듯이 미리 정렬이 되어 있어야 되는 점, 경우에 따라서는 쓰기 곤란한 경우도 있다는 점이 단점이다. 이를테면 연결 리스트 같은 것에 이진 탐색을 쓰기 곤란하다. 연결 리스트는 자기테이프 같은 구조라 무작위 위치로 점프하질 못하고 앞뒤로 움직이기만 가능하기 때문이다. 물론 약간의 트릭을 쓰면 연결 리스트에서 이진 탐색이 가능하다.
[math({\mathcal O}({\rm lb}\,n))] 의 위력이 감이 잘 안온다면, 4,294,967,296개(약 43억개)의 원소가 있는 리스트에서 원하는 특정 값을 찾아낼 때 최악의 탐색 깊이(찾는 값이 없는 경우)는 딱 32회이다. 그러나 순차 탐색의 최악의 경우는 4,294,967,296회이다. 저게 0부터 순서대로 숫자가 들어있는 리스트라고 할 때 순차 탐색이 이진 탐색보다 빠른 지점은 32까지. 33부터 그 나머지 구간에서는 이진 탐색이 순차 탐색보다 빠르다. 33회의 비교시에는 약 86억개의 자료를 탐색할 수 있다. 우주에 존재하는 모든 원자 개수만큼의 원소를 가지는 리스트를 주어줘도 약 120회 정도만 비교하면 원하는 값을 찾을 수 있다.
'뭐 하러 무식하게 일일이 비교하고 있나, 32를 찾고 싶으면 그냥 리스트의 32번째 원소를 읽으면 되지' 하고 생각하는 분은, 저게 그냥 예시라는 사실을 기억해주기 바란다. 어떤 데이터가 들어가 있는지 모르는 리스트에서 하나 알고 있는 건 그 리스트가 정렬돼 있다는 것뿐이다. 만약 어떤 데이터가 어떤 방식으로 들어가 있는지도 알고 있다면 이것보다 더 빠른 해시 탐색을 사용할 수 있다. 해시 탐색의 시간복잡도는 [math({\mathcal O}(1))]이다. 말 그대로 리스트의 길이에 영향을 받지 않고 항상 일정한(상수) 시간 안에 찾아낸다.
아주 간략하게 예시를 들어보자. 대학생 여러분(특히 이러한 문서라면 높은 확률로 컴퓨터 관련 학과의 대학생)이라면 업다운이라는 술게임, 혹은 놀이를 해보았을 것이다. 숫자 범위를 지정해놓고, 한 사람이 어떤 숫자를 마음속으로 생각하면, 맞히는 사람이 한가지 숫자를 던졌을 때 생각해 둔 숫자가 그 숫자보다 큰지, 혹은 작은지 알려주면서 점점 범위를 줄여 정답을 유추하는 놀이이다. 이 놀이에서 가장 빠르고 효율적으로 정답을 찾아내는 방법이 무엇일까? 바로 범위의 중간값에 위치한 수를 던지는 것이다. 범위가 1부터 100이라고 한다면 처음엔 50, 그보다 크다고 하면 75, 그보다 작다고 하면 62... 이런 식이다. 이 역시 이진 탐색의 한 가지 좋은 예시로서, 자연수는 기본적으로 개념 자체가 순서대로 정렬되어있는 개념이기 때문에 이것을 써먹을 수 있는 것이다.
3. 제곱근
제곱근에 대한 실수값을 조사하는 방법에서 이러한 알고리즘은 순방향과 역방향에서 동시에 그리고 빠르게 근사값에 접근해감으로써 양쪽 방향에서 범위를 좁혀가는 강력한 수치해석방법으로 이진 탐색 알고리즘(binary search algorithm)으로 정교하게 구현되어 질수있다.찾고자 하는 제곱근 보다 작은 정수와 큰 정수 사이의 예상되는 중간값에서 분할된 근사치에서 에 수렴시킴으로서 에 접근하게 된다.
여기서 는 보다 작은 인접한 정수이다.
예를 들어 의 근사값은 다음과 같이 조사할수있다.
우선 얻고자 하는 값의 수렴은 가 된다.
이 2보다 큰 어떤 수임을 확인되었다. 이제 소수점 이하 부분을 차근차근 탐색한다.
ㅡ 이진 탐색에 의해 중간값(2.5)부터 조사한다.
ㅡ 여기서 이 7을 초과했다! 7의 제곱근은 2.6과 2.7 사이의 값임이 확인되었다.
ㅡ 이진 탐색에 의해 중간값(2.65)부터 조사한다. 여기서 2.65보다는 작은 수임이 확인되었다.
ㅡ 이진 탐색에 의해 중간값(2.625)부터 조사한다.
ㅡ 여기서 7의 제곱근은 2.64와 2.65 사이의 값임이 확인되었다.
ㅡ 이진 탐색에 의해 중간값(2.645)부터 조사한다.
ㅡ 여기서 이 7을 초과했다! 7의 제곱근은 2.645와 2.646 사이의 값임이 확인되었다.
이하 동일한 과정을 반복한다.
ㅡ 이진 탐색에 의해 중간값(2.6455)부터 조사한다.
ㅡ 이진 탐색에 의해 중간값(2.64565)부터 조사한다.
이렇게 접근하는 에서 일치하는 의 자릿수는 이진 탐색 알고리즘으로 얻어진 근사값의 정확한 자릿수를 보여준다.
물론 바빌로니아법이 더 빠르다. 이진탐색은 탐색 범위의 오차를 절반으로 줄이지만, 바빌로니아법에서는 탐색범위의 오차가 (오차시작값)으로 줄어든다.
[1]
정의 출처: "우리말샘 - 이진 탐색 알고리즘" 등
[2]
큰 값 작은 값 조건은 있는데 같은 값 조건이 없다고 생각하는 분은 알고리즘의 위쪽을 보라. 같은 값이면 찾는 값이다.
[3]
이진 탐색의
계산복잡도는
[math({mathcal O}({rm lb},n))](단, [math({\rm lb}\,n = \log_2 n)]), 순차 탐색이 [math({\mathcal O}(n))]이다.