1. [left, right]가 check(left) != check(right)가 되도록 구간 설정
즉, True, False가 반대여야 한다.
2.
while(left + 1 < right)
-> left와 right 사이에 다른칸이 존재하는가?
mid = (left + right) / 2
Check(mid) = Check(left)이면
left = mid;
아니라면
right = mid;
3. 구한 경계에서 답이 left인지 right인지 생각해보고 출력
최대를 최소화
F F F F T T T T -> right가 정답
최소를 최대화
T T T T F F F F -> left가 정답
left, right는 항상 정답의 범위를 나타낼 수 있도록 해야한다.
배열을 출력하는 이분 탐색의 경우
left = -1, right = n으로 설정!!
lower_bound, upper_bound 직접 구현
F F F T T -> right가 정답이 된다.
0 ~ n -1이 right의 정답으로 가능하므로
left = -1, right = n을 넣는다.
<소스 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// F F F T T
// right가 정답
int LowerBound(const vector<int>& v, int x) {
int left = -1;
int right = (int)v.size();
while (left + 1 < right) {
int mid = (left + right) / 2;
if (v[mid] >= x)
right = mid;
else
left = mid;
}
return right;
}
|
cs |
upper_bound는 등호 빼면 끝