[알고리즘] 이분탐색

배열에서 특정한 수를 찾으려면 어떻게 할까?

앞에서부터 하나씩 찾아보면 될 것이다.

arr = [9,3,7,5,6,2,0]
x = 3
for i in arr:
  if x == i:
    print("찾았다")

최악의 경우는 배열 끝에서 찾은 경우이므로 $O(n)$만큼 시간이 걸릴 것이다.

만약 배열이 정렬되어 있다면 더 빠른 시간 안에 찾을 수 있다.

 

만약 배열이 arr = [1,3,5,7,8,9,10]이 있다고 하자.

이 배열에서 8이 있는지 찾고 싶다.

그럼 위 코드를 사용하여 찾는다면 찾는데 5번의 탐색이 필요하다.

하지만 정렬이 되어 있으니 다른 방법을 사용해보자.

우선 배열의 가운데 값을 선택한다.

만약 선택한 값이 찾는 값이라면 그대로 반환하고 아니라면 찾는 수보다 큰지 작은지 판별한다.

정렬이 되어있는 경우를 가정하니까 선택한 수가 크다면 그 수보다 작은 부분은 더 찾을 필요가 없다.

반대로 작다면 큰 부분을 찾을 필요가 없다.

찾을 필요가 없는 부분을 없애고 다시 가운데 값을 선택하여 찾을때까지 반복한다.

 

이 방법을 사용하면 3번만에 찾을 수 있다.

배열이 작아서 큰 차이는 없지만 크기가 커질경우 눈에 띄게 줄어든다.

그 시간복잡도는 $O(log n)$이 된다.

8을 찾는 과정

중요한점은 배열이 정렬되어 있어야 하고 정렬되어 있지 않다면 선형탐색이 빠르다.(정렬하는데 시간이 $O(nlog n)$이기 때문)

 

파이썬과 C++는 이분탐색 모듈을 제공한다.

from bisect import bisect_left, bisect_right
a = [1,3,5,7,8,9,10]
print(bisect_left(a, 8))
# 4
print(bisect_right(a, 8))
# 5
print(bisect_left(a, 2))
# 1
print(bisect_right(a, 2))
# 1

bisect_left는 값이 일치하면 그 인덱스를 반환하고 bisect_right는 인덱스 + 1을 반환해준다.

일치하는 값이 없다면 그 값이 들어가야 할 위치를 반환한다.

int main() {
	vector<int> a({ 1,3,5,7,8,9,10 });
	cout << lower_bound(a.begin(), a.end(), 8) - a.begin() << endl; // 4
	cout << upper_bound(a.begin(), a.end(), 8) - a.begin() << endl; // 5
	cout << lower_bound(a.begin(), a.end(), 2) - a.begin() << endl; // 1
	cout << upper_bound(a.begin(), a.end(), 2) - a.begin() << endl; // 1
}

bisect_left - lower_bound, bisect_right - upper_bound 가 서로 대응된다.