二分探索を実装する

この動画では、線形探索 と 二分探索 の実装方法と、その違いについて学びました。

この演習では、binary_search() 関数を実装します。挑戦してみましょう。

この演習はコースの一部です

Pythonで学ぶデータ構造とアルゴリズム

コースを見る

演習の手順

探索する値が真ん中の値と等しいかを確認します。
探索する値が真ん中の値より小さいかを確認します。
last を middle マイナス 1 の値に設定します。

実践的なインタラクティブ演習

このサンプルコードを完成させて、この演習に挑戦してみましょう。

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1
  
  while first <= last:
    middle = (first + last)//2
    # Check whether the search value equals the value in the middle
    if ____ == ____:
      return True
    # Check whether the search value is smaller than the value in the middle
    elif ____ < ____:
      # Set last to the value of middle minus one
      ____
    else:
      first = middle + 1
  return False
  
print(binary_search([1,5,8,9,15,20,70,72], 5))

コードを編集して実行