들어가면서

오늘 무사히 해낸다면, 작심3일을 한번 해낸 것이겠죠??

이분 탐색(이진 탐색)

• 아이디어 : 이미 정렬된 배열에서 원하는 값을 중간값과 비교하면서 탐색
• 시간 복잡도 : O(log n)

대표적인 유형

• 정수 탐색 : 배열에서 특정 수 찾기
• 조건 만족 탐색 : 최소?, 최대?
• Lower Bound / Upper Bound: 처음/마지막 위치 찾기

사실 이분 탐색 자체는 쉬운 알고리즘이에요
그렇지만, lower_bound/upper_bound는 은근 조건식이 까다로워서 한 번 정리를 하지 않으면 못 풀겠더라고요.

---

경계선를 찾는 이분 탐색 (lower_bound / upper_bound)

lower_bound / upper_bound 는 단순히 최대값, 최소 값이 아니라 x 이상(>=)이 처음으로 나오는 위치와 x 초과(>)가 처음 나오는 위치이다.

해당 값으로 첫 등장 인덱스번호, 마지막 인덱스 번호, 두가지를 사용해서 값의 개수를 셀 수도 있다.

일단 각각의 표준 정의부터 알아보자

upper_bound

• upper_bound 란, target보다 큰 값이 처음으로 등장하는 인덱스
• 문제에서 “마지막으로 조건을 만족하는 값”을 찾으라고 할 때

• 예시

  arr = [1, 2, 4, 4, 4, 5]
  upper_bound(4) → 5 (마지막 4 다음 인덱스)  ```
  

• 조건식 패턴

  - 종료 조건 : while s < e:     
  - arr[mid] > x  →  e = mid
  - arr[mid] <= x → s = mid + 1

lower_bound

• lower_bound 란, target과 크거나 같은 값이 처음으로 등장하는 인덱스
• 문제에서 “처음으로 조건을 만족하는 값”을 찾으라고 할 때

• 예시

  arr = [1, 2, 4, 4, 4, 5]
  lower_bound(4) → 2 (첫 번째 4의 인덱스)

• 조건식 패턴:

  - 종료 조건 : while s < e:     
  - arr[mid] >= x  → e = mid  : 해당 값이 같은 경우 처음으로 등장한 인덱수 일 수 있다.
  - arr[mid] < x → s = mid + 1

백문이 불여 일타 !!

조건식을 실제로 적용해보자

1. 단순 이분 탐색처럼 해보기

인덱스 : 0 1 2 3 4 5
값    : 1 2 4 4 4 5 

3의 upper_bound: 2 = 3보다 큰 수가 처음으로 등장한 인덱스⭐️

이분 탐색의 조건식은 보통 +-1 을 하며 mid값을 조정한다.

• arr[mid] > x → e = mid
• arr[mid] <= x → s = mid + 1

1회차 : 1 2 4 4 4 5 
       s   m     e  : 4 > 3 ==> e = m - 1

2회차 : 1 2 4 4 4 5 
       s e 
       m             : 3 > 2 ==> s = m + 1 
       
3회차 : 1 2 4 4 4 5 
         s,e,m        ==> 1번 인덱스가 나옴  

예상한 2가 아닌 1이 나왔다. 왜그런걸까??

1회차에서 mid값이었던 4이 3보다 큰 수 중에 처음으로 등장한 수일 수도 있었다는 사실을 간과했기 때문이다.
따라서, 비교값이 타겟값보다 큰 경우에 해당 값을 범위에서 제외하지말고 포함시키기 위해 e = mid 해야한다.

2. upper_bound에는 arr[mid] > x → e = mid를 쓰자.

1회차 : 1 2 4 4 4 5 
       s   m     e   : 3 < 4 ==> e = m

2회차 : 1 2 4 4 4 5 
       s   e
         m             : 3 >= 2 ==> s = m + 1 
       
3회차 : 1 2 4 4 4 5 
         s e           : 3 >= 2 ==> s = m + 1 
         m

4회차 : 1 2 4 4 4 5 
           s
           e           : 3 < 4 ==> e = m
           m

그러면 4에 대해서도 생각해보자. (값이 값은 경우)

인덱스 : 0 1 2 3 4 5
값    : 1 2 4 4 4 5 

4의 upper_bound: 5 = 4보다 큰 수가 처음으로 등장한 인덱스⭐️

따라서 이 경우에 비교값이 같은 경우에는 큰 수는 무조건 mid보다 오른쪽에 있기 때문에
s = mid + 1 연산을 한다.

초 간단 정리

• “x 이상 중 제일 작은 값” → lower_bound(x) (= 첫 위치)
• “x 초과 중 제일 작은 값” → upper_bound(x)
• “x 이하 중 제일 큰 값” → upper_bound(x) - 1 (= 마지막 위치)
• “x 미만 중 제일 큰 값” → lower_bound(x) - 1
• “x의 개수” → upper_bound(x) - lower_bound(x)

조건식 기반 경계 탐색

지금까지의 lower_bound / upper_bound는 "정렬된 배열 안에서 값의 경계"를 찾았다면,
코딩 테스트에서는 배열 원소가 아닌 조건을 만족하는 경계값을 찾는 문제도 매우 자주 나온다.
이를 흔히 파라메트릭 서치(Parametric Search)라고 부른다.

예시: 백준 2805 나무 자르기

• 절단기 높이 H를 정했을 때, 잘라낸 나무 합이 M 이상이면 "가능", 아니면 "불가능".
• 가능한 H 중 가장 큰 값을 찾는 문제 → 조건을 만족하는 경계의 마지막 위치를 찾는 것.
• 즉, 배열에서 upper_bound(x) - 1을 구하는 패턴과 똑같다.

조건식 기반 경계 탐색의 일반 구조

l, r = 0, MAX   # 탐색 범위 (예: 절단기 높이)
ans = -1
while l <= r:
    mid = (l + r) // 2
    if condition(mid):       # 조건 만족 → 더 오른쪽으로
        ans = mid            # 후보 저장
        l = mid + 1
    else:                    # 조건 불만족 → 왼쪽으로
        r = mid - 1
# ans = 조건을 만족하는 최댓값

• condition(mid) : 문제마다 정의 (ex. "잘라낸 나무 길이 >= M")
• 만족하는 값 중 가장 큰 값 → "마지막 true" → upper_bound - 1 패턴
• 반대로 "처음으로 true"가 필요하다면 → lower_bound 패턴을 쓰면 된다.

정리

• 배열 내 경계 찾기 → lower_bound, upper_bound
• 조건식 경계 찾기 → 파라메트릭 서치 (원리적으로 동일, 대상이 "배열 원소"가 아니라 "조건식")

즉,

• 첫 등장 → lower_bound 패턴
• 마지막 등장 → upper_bound - 1 패턴
• 조건 만족 최소/최대 → 파라메트릭 서치 (조건식 기반 이분 탐색)