[TIL] 250531 - 이분탐색(Lower Bound / Upper Bound / Custom Bound)

🧩 1. Lower Bound

• 이분탐색에서 원하는 값(target) 이상이 처음 등장하는 위치를 찾는 것

예시

arr = [13, 35, 40, 56, 56, 56, 59, 60, 62, 84]

• 위와 같은 배열이 정렬되어 있다고 할 때,  
  • target = 56 일 때, 처음으로 56이 나오는 위치는 index 3 → Lower Bound(56) = 3
  • 이걸 찾는게 이진 탐색에서 lower bound

Lower Bound 코드

def lower_bound(arr, target):
    left = 0
    right = len(arr) - 1
    min_idx = len(arr)  # 최대 index + 1로 초기화

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] >= target:
            min_idx = mid        # 조건 만족하는 인덱스 저장
            right = mid - 1      # 더 왼쪽에도 있을 수 있으므로 이동
        else:
            left = mid + 1

    return min_idx

• arr[mid] >= target이면 조건을 만족하므로 저장하고 왼쪽으로 더 탐색을 함
• 결국 조건을 처음으로 만족하는 위치가 정답이 됨
• 존재하지 않으면 len(arr) 반환 (즉, 끝까지 없음)
  
  

---

🧩2. Upper Bound

• 원하는 값(target)을 초과하는 값이 처음 등장하는 위치를 찾는 것

예시

arr = [13, 35, 40, 56, 56, 56, 59, 60, 62, 84]

• 위와 같은 배열이 정렬되어 있다고 할 때, 
  • target = 56 일 때, 처음으로 56를 초과하는 값 59이 있는 위치는 index 6 → Upper Bound(56) = 6

Upper Bound 코드

def upper_bound(arr, target):
    left = 0
    right = len(arr) - 1
    min_idx = len(arr)  # 최대 index + 1로 초기화

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] > target:
            min_idx = mid        # 조건 만족 → 정답 후보
            right = mid - 1
        else:
            left = mid + 1

    return min_idx

• Lower Bound와의 차이점
  • >= 조건 → lower bound
  • > 조건 → upper bound
  • Upper Bound - Lower Bound = 특정 값(target)의 개수

---

🧩3. Custom Bound

• 원하는 값 이하의 값이 마지막으로 나오는 위치를 찾는 것

예시

arr = [13, 35, 40, 56, 56, 56, 59, 60, 62, 84]

• target = 56 일 때,  마지막으로 56이 나오는 위치는 index 5 → Custom Bound(56) = 5

Custom Bound 코드

def custom_bound(arr, target):
    left = 0
    right = len(arr) - 1
    max_idx = -1  # 존재하지 않을 경우 -1 반환

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            max_idx = mid        # 조건 만족 → 일단 저장
            left = mid + 1       # 더 오른쪽에도 있을 수 있음
        else:
            right = mid - 1

    return max_idx

• 조건을 만족하는 값 중 가장 오른쪽에 있는 값을 구할 때 주로 쓰임( 즉, 마지막으로 조건을 만족하는 인덱스가 필요할 때 )

---

개념	의미	조건	반환되는 위치
Lower Bound	이상 값의 첫 등장	arr[mid] >= target	첫 번째 만족 위치
Upper Bound	초과 값의 첫 등장	arr[mid] > target	다음 초과 위치
Custom Bound	이하 값의 마지막 등장	arr[mid] <= target	마지막 만족 위치