이분탐색

1. 시간 복잡도

O(logN)

lower bound 및 upper bound는 모두 경계값을 찾는 함수다. 이 함수는 반드시 정렬이 된 값들에서만 사용할 수 있다.

정렬할 값

찾는 값 찾기

2. lower bound

찾고자 하는 값이 가장 처음으로 나오는 위치를 찾는 함수

찾고자 하는 값에 집중한다.

탈출 조건 left ≤ right

mid를 줄여야 하면 → right = mid - 1

mid를 늘여야 하면 → left = mid + 1

mid가 찾고자 하는 값이면 → right = mid

mid에 있는 값을 기준으로 판별

3. upper bound

찾고자 하는 값보다 큰 값이 가장 처음으로 나오는 위치를 찾는 함수

큰값에 집중한다 mid가 같거나 큰값이면 무조건 고려해 준다.

탈출 조건 left < right

mid를 줄이거나 같으면 → right = mid

mid를 늘여야 하면 → left = mid + 1

mid에 있는 값을 기준으로 판별