Algorithm

binary search

algorithm, binary search, python

  • Binary search(이진 탐색)

    • 데이터의 집합이 반드시 정렬된 상태어야 함
    • 시작 인덱스와 끝 인덱스 그리고 중간 인덱스를 정의
    • 원하는 인덱스가 중간 인덱스보다 작다면 끝 인덱스를 중간 인덱스보다 작게 만든다.
    • 원하는 인덱스가 중간 인덱스보다 크다면 시작 인덱스를 중간 인덱스보다 크게 만든다.

    • 시작 인덱스가 끝 인덱스보다 커지면 반복을 멈춘다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      def binary_search(li, target):
          """
          binary_search(li, target) -> idx
          반환값은 target이 있다면 target의 인덱스
          target이 없다면 None을 반환
          """

          start_idx = 0
          end_idx = len(li) - 1

          
          while start_idx <= end_idx:
              mid_idx = (start_idx + end_idx) // 2

              
              if li[mid_idx] == target:
                  return mid_idx
              elif li[mid_idx] > target:
                  end_idx = mid_idx - 1
              else:
                  start_idx = mid_idx + 1

          return None


      li = [3, 5, 7, 8, 9, 11, 12]
      binary_search(li, 8)
      >> 3

      print(binary_search(li,13))
      >> None
Share