주의사항

while (l != r) {

           const int m = l + (r - l) / 2;

           if (array[m] < key) {

                     // ...

           } else if (array[m] == key) {

                     // ...

           } else {

                     // ...

           }

}

이렇게 3가지 경우를 고려하는 방식을 사용하면 안된다. 항상 구간을 true, false로 2가지로 나눠서 생각해야합니다.

이분 탐색 구현

이분 탐색은 False / True 두 개로 분할하여 분할 경계의 위치를 O(logN)에 찾아주는 알고리즘입니다. 첫번째 True를 찾는 코드입니다.

int first_true(int MIN, int MAX) {
	int l = MIN, r=MAX+1;
	while (l != r) {
		int m = l + (r - l) / 2 // (l+r)/2는 오버플로우 위험과 
						// l+r이 int범위를 초과할 경우 음수로 
						//오버플로우 돼서 나누가 2가 다르게 동작하기 때문에 때문에 안됩니다.
		f(m) ? r = m : l = m + 1; // 결과에 따라 남은 구간을 반으로 줄입니다.
	}
	return l; // 미확인 구간이 없어지면 첫번째 True는 바로 그다음 위치입니다.
}

lower_bound

x보다 크거나 같은 원소의 첫 번째 위치

int* lower_bound(int* lo, int* hi, int x) {
           while (lo != hi) {
                     int* const mid = lo + (hi - lo) / 2;
                     *mid >= x ? hi = mid : lo = mid + 1;

           }

           return lo;

}

upper_bound

x보다 큰 원소의 첫번째 위치

int* upper_bound(int* lo, int* hi, int x) {
           while (lo != hi) {
                     int* const mid = lo + (hi - lo) / 2;
                     *mid > x ? hi = mid : lo = mid + 1;
           }
           return lo;
}