[알고리즘] 이진 탐색 알고리즘 (Binary Search)

이진 탐색

이진탐색은 정렬된 배열이나 리스트에서 특정 값을 찾는 효율적인 알고리즘으로, 정렬된 데이터에서만 사용할 수 있다. 이진탐색 트리의 삽입 시 정렬 알고리즘과 유사하다. O(logN)의 시간복잡도를 가지며, 정렬과 함께 사용하면 O(NlogN)의 시간복잡도를 가진다. 탐색을 한 번만 할 때는 선형 탐색O(N)이 더 빠르지만, 여러 번 해야 할 때는 이진탐색O(logN)이 더 효율적이다.

과정

1. 중간값을 선택한다.

2. 찾고자 하는 값과 비교한다.

3. 찾고자 하는 값과 같다면 종료.

4. 찾고자 하는 값보다 작다면 배열의 중간값 기준 왼쪽에서 탐색을 계속한다.

5. 찾고자 하는 값보다 크다면 배열의 중간값 기준 오른쪽에서 탐색을 계속한다.

6. 살펴보는 범위를 절반 씩 줄여가며 위 과정을 답을 찾을 때 까지 반복한다.

사용

C++에서 정렬에 사용되는 함수로 std::sort가 있고, 이진탐색에 사용되는 함수로 std::binary_search, std::lower_bound, std::upper_bound 가 있다.

[STL] 8. binary_search

ㅤ	std::binary_search	std::lower_bound	std::upper_bound
반환 위치	x	찾는 값 이상의 값 중 처음	찾는 값 초과하는 값 중 처음
반환 값	bool	iterator	iterator

중복값 확인 예시

vector<int> v = {0, 1, 2, 3, 3, 4};
int three = upper_bound(v.begin(), v.end(), 3) - lower_bound(v.begin(), v.end(), 3);
//랜덤 액세스 컨테이너에서는 이터레이터 간의 차이를 구하는 연산 가능
cout << "num of three: " << three << endl; //2

파라메트릭 서치

최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법이다. 쉽게 설명하자면, bool형 함수를 이용해 이진탐색을 진행하는 방법이다.

bool Avail(){};

while(left <= right) {
	if (Avail()) {
		left = mid + 1;
	} else{
		right = mid - 1;
	}
	mid = left + right;
}