logo

TechCodeview

二分探索のための Python プログラム (再帰的および反復的)

簡単に言うと、この検索アルゴリズムは、1 回の比較で要素の半分を無視することですでに並べ替えられている要素のコレクションを利用します。

  1. x を中央の要素と比較します。
  2. x が中間要素と一致する場合、中間インデックスを返します。
  3. それ以外の場合、x が中間要素より大きい場合、x は中間要素の後の右 (大きい) 半分のサブ配列にのみ存在できます。次に、右半分にアルゴリズムを再度適用します。
  4. それ以外の場合、x が小さい場合、ターゲット x は左 (下) 半分になければなりません。そこで、左半分にアルゴリズムを適用します。

再帰的二分探索のための Python プログラム

Python3








# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> ># Check base case> >if> high>>>=> low:> >mid>=> (high>+> low)>/>/> 2> ># If element is present at the middle itself> >if> arr[mid]>=>=> x:> >return> mid> ># If element is smaller than mid, then it can only> ># be present in left subarray> >elif> arr[mid]>×：>> return> binary_search(arr, low, mid>-> 1>, x)> ># Else the element can only be present in right subarray> >else>:> >return> binary_search(arr, mid>+> 1>, high, x)> >else>:> ># Element is not present in the array> >return> ->1> # Test array> arr>=> [>2>,>3>,>4>,>10>,>40> ]> x>=> 10> # Function call> result>=> binary_search(arr,>0>,>len>(arr)>->1>, x)> if> result !>=> ->1>:> >print>(>'Element is present at index'>,>str>(result))> else>:> >print>(>'Element is not present in array'>)> 



>

コンピュータネットワークのネットワーク層 

>

ぎこちないリンスペース
出力 

Element is present at index 3>

時間計算量 : O(log n)

補助スペース : O(logn) [注意: 再帰により呼び出しスタックが作成されます]

反復を使用した二分探索のための Python プログラム

Python3




# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> >low>=> 0> >high>=> len>(arr)>-> 1> >mid>=> 0> >while> low <>=> high:> >mid>=> (high>+> low)>/>/> 2> ># If x is greater, ignore left half> >if> arr[mid] low = mid + 1 # If x is smaller, ignore right half elif arr[mid]>x: high = Mid - 1 # x が Mid に存在することを意味します else: return Mid # ここに到達した場合、要素は存在しません return -1 # テスト配列 arr = [ 2, 3, 4, 10, 40 ] x = 10 # 関数呼び出しの結果 = binary_search(arr, x) if result != -1: print('要素はインデックスに存在します', str(result)) else: print('要素は配列に存在しません ')>> 

>

>

Java正規表現
出力 

Element is present at index 3>

時間計算量 : O(log n)

補助スペース :O(1)

組み込みの bisect モジュールを使用した二分探索用の Python プログラム

段階的なアプローチ:

  • このコードは、バイナリ検索のサポートを提供する bisect モジュールをインポートします。
  • binary_search_bisect() 関数が定義されており、配列 arr と x を検索する要素を入力として受け取ります。
  • この関数は、bisect モジュールの bisect_left() 関数を呼び出します。この関数は、ソートされた順序を維持するために x を挿入する必要がある、ソートされた配列 arr 内の要素の位置を見つけます。要素が配列内にすでに存在する場合、この関数はその位置を返します。
  • 次に、関数は、返されたインデックス i が配列の範囲内にあるかどうか、およびそのインデックスの要素が x に等しいかどうかをチェックします。
  • 条件が true の場合、関数は配列内の要素の位置としてインデックス i を返します。
  • 条件が false の場合、関数は要素が配列内に存在しないことを示す -1 を返します。
  • 次に、コードは配列 arr と検索する要素 x を定義します。
  • binary_search_bisect() 関数は、arr と x を入力として呼び出して、返された結果は result 変数に格納されます。
  • 次に、コードは結果が -1 に等しくないかどうかをチェックし、要素が配列内に存在することを示します。 true の場合、配列内の要素の位置が出力されます。
  • 結果が -1 に等しい場合、コードは要素が配列内に存在しないというメッセージを出力します。

Python3




import> bisect> > def> binary_search_bisect(arr, x):> >i>=> bisect.bisect_left(arr, x)> >if> i !>=> len>(arr)>and> arr[i]>=>=> x:> >return> i> >else>:> >return> ->1> > > # Test array> arr>=> [>2>,>3>,>4>,>10>,>40>]> x>=> 10> > # Function call> result>=> binary_search_bisect(arr, x)> > if> result !>=> ->1>:> >print>(>'Element is present at index'>,>str>(result))> else>:> >print>(>'Element is not present in array'>)> 

>

>

出力

Javaサーバーページ 
Element is present at index 3>

時間計算量 : O(log n)

補助スペース :O(1)