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 문제 풀었는데 이 내용이 책에 나와서 재밌었다

  • 자세히 살펴볼 수 있어 좋았다

Last updated

Was this helpful?