再帰なしでバイナリ検索を実装するPythonプログラム

辞書を使用せずに二分探索を実装する必要がある場合は、リストの最初と最後のインデックスをチェックし、リストの中間値を取得するメソッドを定義できます。

次に、チェックする必要のある値と比較されます。見つかった場合は、値が返されます。それ以外の場合は、-1が返されます。

バイナリ検索は、昇順または降順のいずれかで、並べ替えられた要素に対してのみ機能することを覚えておくことが重要です。

リストを使用して、異種の値（つまり、整数、浮動小数点、文字列などの任意のデータ型のデータ）を格納できます。

以下は同じのデモンストレーションです-

例

def binary_search(my_list, elem):
   low = 0
   high = len(my_list) - 1
   mid = 0
   while low <= high:
      mid = (high + low) // 2
      if my_list[mid] < elem:
         low = mid + 1
      elif my_list[mid] > elem:
         high = mid - 1
      else:
         return mid
   return -1

my_list = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
elem_to_search = 1
print("The list is")
print(my_list)

my_result = binary_search(my_list, elem_to_search)

if my_result != -1:
   print("Element found at index ", str(my_result))
else:
   print("Element not found!")

出力

The list is
[1, 9, 11, 21, 34, 54, 67, 90]
Element found at index  0

説明

• 「binary_search」という名前のメソッドが定義されており、リストと検索対象の要素をパラメーターとして受け取ります。
• 変数lowは0に割り当てられ、変数midは0に割り当てられます。
• 変数highには、list-1の長さが割り当てられます。
• ビット単位のフロア除算は、値「low」が「high」以下の場合にのみ、「mid」変数の値を取得するために実行されます。
• 最初に、値が中間インデックスに存在する値よりも小さい場合、要素は低インデックスから中インデックスまで検索されます。
• それ以外の場合、値がmidより大きく、highより小さい場合、要素はmidからhighのインデックスで検索されます。
• これで、リストが定義されました。
• メソッドは、上記のリストをパラメーターとして渡すことによって呼び出されます。
• この操作のデータは変数に格納されます。
• この変数は、コンソールに表示される出力です。