5. 이진 탐색

탐색 범위가 2,000만을 넘어가면 해결 방법으로 이진 탐색을 떠올려 보자.
처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 O(logN)의 시간 복잡도를 가진 알고리즘을 생각해봐야 한다.

1. 이진 탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 시간 복잡도

  • O(logN)

2. 이진 탐색 소스코드

재귀적으로 구현

def binary_search(array, target, start, end): # start와 end는 idx 기준
  if start > end:
    return None
  mid = (start + end) // 2
  # mid = int((start + end) / 2)
  
  if array[mid] == target:
    return mid
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  else:
    return binary_search(array, target, mid + 1, end)

# n: 원소의 개수, target: 찾고자 하는 데이터
n, target = list(map(int, input().split()))
# array: 전체 데이터
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)

if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1) # idx가 아니라 순서 기준이면 +1

반복문으로 구현

def binary_search(array, target, start, end): # start와 end는 idx 기준
  while start <= end:
    mid = (start + end) // 2

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

  return None

# n: 원소의 개수, target: 찾고자 하는 데이터
n, target = list(map(int, input().split()))
# array: 전체 데이터
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)

if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1) # idx가 아니라 순서 기준이면 +1

[참고] 3. 파이썬 이진 탐색 라이브러리

• from bisect import bisect_left, bisect_right

• bisect_left(array, x): 배열 array에 원소 x를 삽입할 가장 왼쪽 index 반환

• bisect_right(array, x): 배열 array에 원소 x를 삽입할 가장 오른쪽 index 반환

from bisect import bisect_left, bisect_right

array = [0, 2, 3, 3, 4, 6, 8]

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

---

[참고]

• (이코테 2021 강의 몰아보기) 5. 이진 탐색 (https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5)