[1. 개요]
보통 매우 큰 범위를 갖는 어떤 값 중 최적 값을 찾을 때 유용하다.
- N 이 [0, 1,000,000,000] 사이의 값일 때,
- 어떤 식을 최대 혹은 최소로 만드는 N 을 구한다.
- 완전 탐색 시, 시간 초과가 당연하다.
- 그러나 이 범위에서 이분 탐색을 하면, 32번 이내로 찾을 수 있다.
=> 어떤 조건을 만족하는 최대 N 을 구해야 할 때
=> 먼저 중간 값을 찾고, 이 값을 주어진 식에 대입
=> 특정 조건을 만족하면 상위 구간에서 이분 탐색 진행
=> 만족하지 않으면 하위 구간에서 이분 탐색 진행
주의 할점
- 범위와 반복문 조건이 중요하다. (구간 및, 반복문 조건 (등호 유무) 등이 다르면 틀린다.)
=> 구간은 보통 [a, b], 폐구간 이어야 한다.
=> 그래서 반복문 조건은 while (a <= b) 이어야 한다.
==> 구간이 [a, b) 이면, while (a < b);
=> 최적 값이 a 혹은 b 가 될 수 있기 때문이다. - 정리하면, N의 최대 값을 찾아야 할 때
1. 구간: [a, b] 일 때
2. 반복문: while (a <= b);
=> mid = (a+b) / 2
=> 조건 만족: a = mid + 1
=> [mid+1, b]
=> 조건 불만족: b = mid - 1
=> [a, mid-1]
=> mid 는 다음 반복문 전 여기서 검사했으므로 다음 탐색에서 제외해야 한다.
결정 문제로 바꿔서 풀어야 할 때
- 어떤 최적값을 구해야 할 때,
- 최적값을 이분 탐색으로 설정해가면서, 이 값을 통해 어떤 조건을 만족하는지 확인 해야 할 때 사용 할 수 있다.
[2. 예제]
