06_searching.py - Examples

  1"""
  2이분 탐색 (Binary Search)
  3Binary Search Algorithms
  4
  5정렬된 데이터에서 O(log n) 시간에 검색하는 알고리즘입니다.
  6"""
  7
  8from typing import List, Optional
  9import bisect
 10
 11
 12# =============================================================================
 13# 1. 기본 이분 탐색
 14# =============================================================================
 15def binary_search(arr: List[int], target: int) -> int:
 16    """
 17    정렬된 배열에서 target의 인덱스 찾기
 18    없으면 -1 반환
 19    시간복잡도: O(log n)
 20    """
 21    left, right = 0, len(arr) - 1
 22
 23    while left <= right:
 24        mid = left + (right - left) // 2  # 오버플로우 방지
 25
 26        if arr[mid] == target:
 27            return mid
 28        elif arr[mid] < target:
 29            left = mid + 1
 30        else:
 31            right = mid - 1
 32
 33    return -1
 34
 35
 36def binary_search_recursive(arr: List[int], target: int, left: int, right: int) -> int:
 37    """이분 탐색 (재귀 버전)"""
 38    if left > right:
 39        return -1
 40
 41    mid = left + (right - left) // 2
 42
 43    if arr[mid] == target:
 44        return mid
 45    elif arr[mid] < target:
 46        return binary_search_recursive(arr, target, mid + 1, right)
 47    else:
 48        return binary_search_recursive(arr, target, left, mid - 1)
 49
 50
 51# =============================================================================
 52# 2. Lower Bound / Upper Bound
 53# =============================================================================
 54def lower_bound(arr: List[int], target: int) -> int:
 55    """
 56    target 이상인 첫 번째 요소의 인덱스
 57    모든 요소가 target보다 작으면 len(arr) 반환
 58    """
 59    left, right = 0, len(arr)
 60
 61    while left < right:
 62        mid = left + (right - left) // 2
 63        if arr[mid] < target:
 64            left = mid + 1
 65        else:
 66            right = mid
 67
 68    return left
 69
 70
 71def upper_bound(arr: List[int], target: int) -> int:
 72    """
 73    target 초과인 첫 번째 요소의 인덱스
 74    모든 요소가 target 이하이면 len(arr) 반환
 75    """
 76    left, right = 0, len(arr)
 77
 78    while left < right:
 79        mid = left + (right - left) // 2
 80        if arr[mid] <= target:
 81            left = mid + 1
 82        else:
 83            right = mid
 84
 85    return left
 86
 87
 88def count_occurrences(arr: List[int], target: int) -> int:
 89    """특정 값의 등장 횟수"""
 90    return upper_bound(arr, target) - lower_bound(arr, target)
 91
 92
 93# =============================================================================
 94# 3. 첫 번째/마지막 위치 찾기
 95# =============================================================================
 96def find_first_position(arr: List[int], target: int) -> int:
 97    """target이 처음 등장하는 인덱스 (없으면 -1)"""
 98    idx = lower_bound(arr, target)
 99    if idx < len(arr) and arr[idx] == target:
100        return idx
101    return -1
102
103
104def find_last_position(arr: List[int], target: int) -> int:
105    """target이 마지막으로 등장하는 인덱스 (없으면 -1)"""
106    idx = upper_bound(arr, target) - 1
107    if idx >= 0 and arr[idx] == target:
108        return idx
109    return -1
110
111
112# =============================================================================
113# 4. 회전 정렬 배열 검색
114# =============================================================================
115def search_rotated(arr: List[int], target: int) -> int:
116    """
117    회전된 정렬 배열에서 검색
118    예: [4, 5, 6, 7, 0, 1, 2] - 원래 [0,1,2,4,5,6,7]을 회전
119    시간복잡도: O(log n)
120    """
121    if not arr:
122        return -1
123
124    left, right = 0, len(arr) - 1
125
126    while left <= right:
127        mid = left + (right - left) // 2
128
129        if arr[mid] == target:
130            return mid
131
132        # 왼쪽 절반이 정렬되어 있는 경우
133        if arr[left] <= arr[mid]:
134            if arr[left] <= target < arr[mid]:
135                right = mid - 1
136            else:
137                left = mid + 1
138        # 오른쪽 절반이 정렬되어 있는 경우
139        else:
140            if arr[mid] < target <= arr[right]:
141                left = mid + 1
142            else:
143                right = mid - 1
144
145    return -1
146
147
148# =============================================================================
149# 5. 최솟값 찾기 (회전 배열)
150# =============================================================================
151def find_minimum_rotated(arr: List[int]) -> int:
152    """회전 정렬 배열의 최솟값 찾기"""
153    left, right = 0, len(arr) - 1
154
155    while left < right:
156        mid = left + (right - left) // 2
157
158        if arr[mid] > arr[right]:
159            left = mid + 1
160        else:
161            right = mid
162
163    return arr[left]
164
165
166# =============================================================================
167# 6. 제곱근 구하기 (정수)
168# =============================================================================
169def integer_sqrt(n: int) -> int:
170    """
171    n의 정수 제곱근 (버림)
172    예: sqrt(8) = 2
173    """
174    if n < 0:
175        raise ValueError("음수의 제곱근은 정의되지 않습니다")
176    if n == 0:
177        return 0
178
179    left, right = 1, n
180
181    while left <= right:
182        mid = left + (right - left) // 2
183        square = mid * mid
184
185        if square == n:
186            return mid
187        elif square < n:
188            left = mid + 1
189        else:
190            right = mid - 1
191
192    return right  # floor(sqrt(n))
193
194
195# =============================================================================
196# 7. 매개변수 탐색 (Parametric Search)
197# =============================================================================
198def can_split(arr: List[int], m: int, max_sum: int) -> bool:
199    """
200    배열을 m개 이하의 그룹으로 나눌 때
201    각 그룹 합이 max_sum 이하인지 확인
202    """
203    count = 1
204    current_sum = 0
205
206    for num in arr:
207        if current_sum + num > max_sum:
208            count += 1
209            current_sum = num
210            if count > m:
211                return False
212        else:
213            current_sum += num
214
215    return True
216
217
218def split_array_min_largest_sum(arr: List[int], m: int) -> int:
219    """
220    배열을 m개의 연속 부분 배열로 나눌 때
221    각 부분 배열 합의 최댓값을 최소화
222    시간복잡도: O(n log(sum))
223    """
224    left = max(arr)      # 최소 가능한 값: 가장 큰 요소
225    right = sum(arr)     # 최대 가능한 값: 전체 합
226
227    while left < right:
228        mid = left + (right - left) // 2
229        if can_split(arr, m, mid):
230            right = mid
231        else:
232            left = mid + 1
233
234    return left
235
236
237# =============================================================================
238# 8. Peak Element 찾기
239# =============================================================================
240def find_peak_element(arr: List[int]) -> int:
241    """
242    배열에서 peak element의 인덱스 찾기
243    peak: arr[i] > arr[i-1] and arr[i] > arr[i+1]
244    시간복잡도: O(log n)
245    """
246    left, right = 0, len(arr) - 1
247
248    while left < right:
249        mid = left + (right - left) // 2
250
251        if arr[mid] > arr[mid + 1]:
252            right = mid
253        else:
254            left = mid + 1
255
256    return left
257
258
259# =============================================================================
260# 테스트
261# =============================================================================
262def main():
263    print("=" * 60)
264    print("이분 탐색 (Binary Search) 예제")
265    print("=" * 60)
266
267    # 1. 기본 이분 탐색
268    print("\n[1] 기본 이분 탐색")
269    arr = [1, 3, 5, 7, 9, 11, 13, 15]
270    target = 7
271    result = binary_search(arr, target)
272    print(f"    배열: {arr}")
273    print(f"    {target} 찾기 -> 인덱스: {result}")
274
275    # 2. Lower/Upper Bound
276    print("\n[2] Lower Bound / Upper Bound")
277    arr = [1, 2, 2, 2, 3, 4, 5]
278    target = 2
279    lb = lower_bound(arr, target)
280    ub = upper_bound(arr, target)
281    count = count_occurrences(arr, target)
282    print(f"    배열: {arr}")
283    print(f"    target={target}")
284    print(f"    lower_bound: {lb}, upper_bound: {ub}")
285    print(f"    등장 횟수: {count}")
286
287    # bisect 모듈과 비교
288    print(f"    (bisect_left: {bisect.bisect_left(arr, target)}, "
289          f"bisect_right: {bisect.bisect_right(arr, target)})")
290
291    # 3. 첫 번째/마지막 위치
292    print("\n[3] 첫 번째/마지막 위치")
293    arr = [5, 7, 7, 8, 8, 8, 10]
294    target = 8
295    first = find_first_position(arr, target)
296    last = find_last_position(arr, target)
297    print(f"    배열: {arr}")
298    print(f"    {target}의 첫 위치: {first}, 마지막 위치: {last}")
299
300    # 4. 회전 배열 검색
301    print("\n[4] 회전 정렬 배열 검색")
302    arr = [4, 5, 6, 7, 0, 1, 2]
303    target = 0
304    result = search_rotated(arr, target)
305    print(f"    회전 배열: {arr}")
306    print(f"    {target} 찾기 -> 인덱스: {result}")
307
308    # 5. 회전 배열 최솟값
309    print("\n[5] 회전 배열 최솟값")
310    arr = [4, 5, 6, 7, 0, 1, 2]
311    result = find_minimum_rotated(arr)
312    print(f"    회전 배열: {arr}")
313    print(f"    최솟값: {result}")
314
315    # 6. 제곱근
316    print("\n[6] 정수 제곱근")
317    for n in [4, 8, 16, 17, 100]:
318        result = integer_sqrt(n)
319        print(f"    sqrt({n}) = {result}")
320
321    # 7. 매개변수 탐색
322    print("\n[7] 매개변수 탐색 (배열 분할)")
323    arr = [7, 2, 5, 10, 8]
324    m = 2
325    result = split_array_min_largest_sum(arr, m)
326    print(f"    배열: {arr}, 분할 수: {m}")
327    print(f"    최소 최대합: {result}")
328
329    # 8. Peak Element
330    print("\n[8] Peak Element 찾기")
331    arr = [1, 2, 1, 3, 5, 6, 4]
332    result = find_peak_element(arr)
333    print(f"    배열: {arr}")
334    print(f"    peak 인덱스: {result} (값: {arr[result]})")
335
336    print("\n" + "=" * 60)
337
338
339if __name__ == "__main__":
340    main()