이진 탐색

이진 탐색❓

: 정렬되어 있는 리스트에서 탐색 범위(시작점, 끝점, 중간점)를 절반씩 좁혀가며 데이터를 탐색
vs. 순차 탐색: 리스트 안의 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법

시간 복잡도

O(log2N) : 단계마다 탐색 범위를 2로 나누는 것과 동일
→ 문제에서 N의 범위가 굉장히 넓은 경우가 많음!!

코드

(1) 재귀

def binary_search(arr, target, start, end):
  mid = (start + end) // 2
  # 원소 존재 X
  if start > end:
  	return None
  # 원소 발견
  if arr[mid] == target:
  	return mid
  # 찾는값 < 중간점
  elif target < arr[mid]:
    return binary_search(arr, target, start, mid - 1)
  # 중간점 < 찾는값
  else: return binary_search(arr, target, mid + 1, end)

arr = [1, 3, 5, 7, 9, 11, 12, 15, 17, 19]
# 찾을 원소 13
result = binary_search(arr, 13, 0, len(arr) - 1)

if result == None:
  print('원소가 존재하지 않습니다')
else:
  print(result, '번째 인덱스', arr[result])

(2) 반복

arr = [1, 3, 5, 7, 9, 11, 12, 15, 17, 19]
target = 11

start = 0
end = len(arr) - 1
ans = None

while start <= end:
  mid = (start + end) // 2
  if arr[mid] == target:
    ans = mid
    break
  elif arr[mid] > target:
    end = mid - 1
  else:
    start = mid + 1

print(ans) # 5

---

파라메트릭 서치 (Parametric Search)

: 최적화 문제를 결정 문제(예 / 아니오)로 바꾸어 해결하는 기법
ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
일반적으로 코딩 테스트에서 다음 문제는 이진 탐색을 이용하여 해결할 수 있음

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

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

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