【Python】バイナリサーチの実装

はじめに

与えられた数字のインデックス番号を返すアルゴリズムです（binary_search）。

実装

binary_search.py

from typing import List, NewType

IndexNum = NewType("IndexNum", int)

def linear_search(numbers: List[int], value: int) -> IndexNum:
  for i in range(0, len(numbers)):
    if numbers[i] == value:
      return i
  return -1

# パターン１（該当する数字のインデックス番号を出力）
# def binary_search(numbers: List[int], value: int) -> IndexNum:
#   left, right = 0, len(numbers) - 1
#   while left <= right:
#     mid = (left + right) // 2
#     if numbers[mid] == value:
#       return mid
#     elif numbers[mid] < value:
#       left = mid + 1
#     else:
#       right = mid - 1
#   return -1

# パターン２
def binary_search(numbers: List[int], value: int) -> IndexNum:
  def _binary_search(numbers: List[int], value: int, left: IndexNum, right: IndexNum) -> IndexNum:
    if left > right:
      return -1
    
    mid = (left + right) // 2
    if numbers[mid] == value:
      return mid
    elif numbers[mid] < value:
      return _binary_search(numbers, value, mid + 1, right)
    else:
      return _binary_search(numbers, value, 0, mid - 1) 

  return _binary_search(numbers, value, 0, len(numbers) - 1)

# テスト
if __name__ == "__main__":
  nums = [0,1,5,6,8,10,25] 
  print(binary_search(nums, 6))

参考