이분탐색(binary Search)에 대해 알아보자
이분탐색
이분 탐색은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 이분 탐색은 분할 정복 알고리즘의 한 예이다.
이분 탐색의 과정
- 배열의 중간을 먼저 탐색한다.
- 중간값이 탐색값이면 중단.
- 중간값이 탐색값이 아니라면 중간값과 탐색값의 크기를 비교한다.
- 중간값 > 탐색값 - 중간값의 오른쪽 인덱스들은 제외
- 중간값 < 탐색값 - 중간값의 왼쪽 인덱스들은 제외
데이터가 정렬되어 있으면 위의 과정을 반복해서 절반씩 나눠서 걸러낸다.
STL algorithm에서 upper_bound와 lower_bound함수를 살펴보면 이분탐색을 기반으로 한 탐색 방법이다. 이분탐색이므로, 배열이나 리스트가 정렬이 되어 있어야 한다. lower_bound의 결과는 key값이 없으면 key값보다 큰 가장 작은 정수 값을 찾는다. 같은 원소가 여러 개 있어도 상관 없으며, 항상 유일한 해를 구할 수 있다. 예를 들어 [begin, end] 배열이 있을 때, 중간위치의 인덱스를 mid라고 하면 arr[mid] < key 이면서 arr[mid] >= key인 최소의 m 값을 찾으면 된다. upper_bound는 반대로 생각하면 된다.
반환형은 Iterator이므로 vector를 사용하게 되면 벡터의 begin()을 빼게 되면 인자의 순서를 구할 수 있고, 배열이라면 첫 번쨰 주소를 빼면 인자의 순서를 알 수 있다.
시간 복잡도는 O(log(last - first))으로, 전체 원소 개수에 로그에 비례한다.