이분 탐색
- 배열이 정렬되어 있어야 사용 가능
- 반으로 쪼개면서 탐색함
- 시간 복잡도 O(logN) (순차 탐색은 O(N))
- 시작점, 중간점, 끝점을 가리키는 변수를 가짐
- 재귀, 반복문으로 구현 가능
1. 시작점, 중간점, 끝점 (left, mid, right) 정하기
2. 중간점과 찾는 값 비교 후 작으면 right를 mid-1로, 크면 left를 mid+1로 한 후 mid 값 다시 정하기
3. 2번을 반복
Parametric Search
- 최적화 문제를 결정 문제로 바꿔 푸는 것
- 이분 탐색으로 결정 문제를 해결하면서 범위를 줄여 최솟값, 최댓값을 찾음
- 결정 문제인지 아닌지의 차이 (이분탐색과)
1. left, mid, right를 정한 후 mid가 조건을 만족하는지 확인
2. 만족하지 않으면 mid 이전의 값들은 모두 만족 X, 만족하면 이후 값들은 모두 만족 O -> left, right, mid 값 조정
3. 2번을 반복
4. 마지막 mid 값이 최솟값 / 최댓값이 됨
(left==right 상황에서 조건 만족하는지 확인, 만족하면 그 값이 O, 아니면 그 이후/ 이전 값이 정답)
이분 탐색 특징
- 입력 데이터가 많거나 탐색 범위가 매우 넓은 편
- 데이터 개수가 1000만개 이상 또는 탐색 범위 크기가 1000억 이상일 경우 이진 탐색 알고리즘이 해결법일 수 있음
