이진 탐색

탐색 전에 반드시 정렬되어 있어야하고, 범위를 절반씩 줄여가면서 답을 찾아야한다.

시간복잡도

따라서 정렬 O(NlogN) + 이진탐색 O(logN) -> 결과적으로 O(NlogN).

즉, 경우에 따라서 선형탐색 O(N) 이 더 좋은 선택이 될 수도 있다.

하지만 여러번 탐색을 해야하는 경우라면, 그 탐색의 횟수가 N번이라면, 선형 탐색의 경우에는 N * O(N) = O(N^2) 이 된다. 그러나 이진 탐색을 하면, 정렬 O(NlogN) + N * O(logN) = O(NlogN)이 된다.

결론

결과적으로 탐색을 한번만 하는 경우에는 굳이 정렬을 해가면서 이진탐색을 사용할 이유가 없다.

하지만 탐색을 여러번 해야하는 경우에는 정렬 한번 해두고, 이진탐색을 해주는게 더 빠를 수 있다.

C++ lower/upper_bound

upper_bound(v.begin(), v.end(), 3); -> 벡터 중에서 3이상의 값중에 제일 첫번째 index

lower_bound(v.begin(), v.end(), 3); -> 벡터 중에서 3초과 값중에 제일 첫번째 index

upper_bound - lower_bound -> 벡터중에서 3의 개수

python bisect_left/right

사용법: from bisect import bisect_left, bisect_right

Parametric Search

최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법이다.

• 최적화 문제(Optimization Problem) : 문제 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제
• 결정 문제(Decision Problem) : yes or no problem
• 매개변수 parameter가 주어지면 true or false가 결정되어야한다.
• 가능한 해의 영역이 연속적이어야 한다.
• 범위를 반씩 줄여가면서 가운데 값이 true인지 false인지 구한다.

결론적으로 이진 탐색은 특정한 값을 찾는 알고리즘이라면, parametric search는 경계값을 찾는 알고리즘이다.