이진 탐색

• 순차 탐색 : 앞에서부터 데이터를 하나씩 확인
• 이진 탐색 : 탐색 범위를 절반씩 좁혀가며 탐색
  • 정렬된 상태에서 시작
  • O(logN)
  • 입력이 말도 안되게 큰 편
    • 예: 업다운 게임

반복문

def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None


arr = [1, 2, 3, 4, 5, 6, 7, 8]
result = binary_search(arr, 4, 0, len(arr) - 1)
print(result)

재귀

def binary_search(arr, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, start, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, end)


arr = [1, 2, 3, 4, 5, 6, 7, 8]
result = binary_search(arr, 4, 0, len(arr) - 1)
print(result)

파이썬 라이브러리

• bisect_left(a, x) : 정렬 순서 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a, x) : 정렬 순서 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

from bisect import bisect_left, bisect_right

a = [1, 2, 3, 3, 4, 5]

print(bisect_left(a, 3))  # 2
print(bisect_right(a, 3))  #4 

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right


def count_by_range(arr, left, right):
    right_idx = bisect_right(arr, right)
    left_idx = bisect_left(arr, left)
    return right_idx - left_idx


arr = [1, 2, 3, 3, 4, 4, 4, 5, 6, 7]

# 3 데이터 개수
print(count_by_range(arr, 3, 3))  # 2

# -1 ~ 3 범위 데이터 개수
print(count_by_range(arr, -1, 3))  # 4

Parametric Search

• 최적화 문제를 결정 문제(Yes or No)로 바꾼다.
  • 이진 탐색으로 해결 가능