Chapter 2: 이진 탐색

내용 정리

선형 스캔

• 탐색 방식

  • list에서 한 번에 하나씩 값을 비교하면서 목푯값을 찾거나, 목록의 끝에 도달할 때까지 비교해 목푯값을 찾는다

• 단점

  • 원소가 아주 많은 리스트에서 비효율적이다

이진 탐색 알고리즘

• 탐색 방식

  • list를 반으로 분할하고, 목푯값이 어느쪽 절반에 속하는지 결정한다

  • 목푯값이 포함되지 않는 절반을 버리고, 여전히 목푯값이 있을 수 있는 나머지 절반만 가지고 같은 과정을 반복해 마지막 값만 남을때까지 이를 반복한다

• 특징

  • 정렬된 데이터에서만 작동한다

  • 배열이 오름차순으로 정렬되어 있음을 이용한다

  • 두 경계를 이용해 탐색 공간을 추적한다

    • upper bound → index high

    • lower bound → index low

  • index low가 목푯값을 가리키게 되어도, 중간 지점이 목푯값을 가리킬 때까지 탐색을 계속한다

• 없는 값 처리

  • 목푯값이 리스트에 없는 경우 탐색을 계속 진행하다 보면, 두 경계 중 하나가 항상 중간 index를 넘어가기 때문에 index high < index low 가 되면 탐색을 중단할 수 있다

• 구현

  def binary_search(array: list[int], target: int) -> int:
    start, end = 0, len(array) - 1
  
    while start <= end:
      mid = (start + end) // 2
  
      if array[mid] == target:
        return mid
      elif array[mid] < target:
        start = mid + 1
      else:
        end = mid - 1
  
    return -1

• index 나 이산적인 원소 집합이 존재하지 않는 연속 데이터에 적용

  • 탐색 방식

    • index 대신 값에 대한 upper bound와 lower bound를 이용

    • 범위가 작아질 때 탐색을 종료

      • upper bound - lower bound < threshold

  • 시사점

    • 선형 스캔보다 더 나은 정밀도를 얻을 수 있다

    • 이분법 (bisection search) 등의 수학적 기술의 기초가 된다

      • 이분법은 f(x) = 0인 x 값을 찾기 위해 사용하는데, 0보다 크거나 작은 경계를 추적한다

      • 중앙값에서 구간을 반복하여 절반으로 나눔으로써, 이분법 알고리즘은 함수가 정확히 0이 되는 x값에 접근할 수 있따

• 실행 시간

  	Time Complexity	Space Complexity
  선형 스캔	O(n)	O(1)
  이진 탐색	O(log⁡ n)	O(1) → 반복문 / O(log⁡n) → 재귀

  단, 이진 탐색은 정렬되지 않은 경우 데이터 정렬이 먼저 필요하므로 O(n log n)의 추가 비용 발생

생각

• 오늘 leetcode 에서 binary search 문제 풀었는데 이 내용이 책에 나와서 재밌었다
• 자세히 살펴볼 수 있어 좋았다