이분탐색(Binary Search)

이분탐색이란

 

이분탐색은 N개의 정렬된 수들 중 어떤 값 K의 위치를 찾아내거나, 없다는 것을 판정하는 탐색을 말한다.

 

이분탐색은 O(logN)의 시간 복잡도를 가지고 있다.

 

이분탐색 설명

 

출처: https://www.geeksforgeeks.org/binary-search/

 

위의 그림을 보자.

 

N=10인 배열에서 23을 찾으려고 한다.

 

이때 중간값은 홀수인 경우, 반올림, 반내림하여도 상관없다. 어쨌거나 절반에 가깝기 때문.

 

1단계

 

이제 이 중간값이 23보다 크거나, 작은지, 같은지를 검사한다. 

 

여기서는 중간값은 16이기 때문에, 23보다 작고, 왼쪽에는 찾으려는 값이 없다는 것을 확실히 알 수 있다.

 

그럼 이제 오른쪽을 검사한다.

 

2단계

 

오른쪽에서 중간값은 56이다. 23보다 크기 때문에, 오른쪽은 더이상 볼 필요가 없다.

 

3단계

 

다음 중간값은 38이다. (혹은 23이 되어서, 바로 값을 찾을 수도 있음)

 

38은 찾으려는 값이 아니니, 마지막 남은 5번 인덱스가 답이 된다.

 

만약 값이 하나도 안 남았는데, 못 찾았다면 그 배열에는 존재하지 않는 것이 된다.

 

파이썬에서의 이분 탐색 문법

 

bisect_left(a, x)

 

정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환한다.

 

bisect_right(a, x)

 

정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환한다.

 

파라메트릭 서치(Parametric Search)

 

파라메트릭 서치란 최적화 문제를 결정 문제(’예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법을 말한다.

 

파라메트릭 서치 문제도 이분 탐색을 이용하여 해결할 수 있다.

 

예를 들어, 65세 이상은 지하철을 무료로 사용할 수 있을 때, 사람들의 나이가 정의된 배열에서

 

지하철을 무료로 사용할 수 있는 최소 나이의 인덱스를 찾으라는 문제가 있다.

 

지하철을 무료로 사용할 수 있다. 없다의 결정 문제를 풀 때, 똑같이 이분탐색을 사용할 수 있다.