PYTHON での二分探索

このチュートリアルでは、Python を使用して二分検索アルゴリズムを適用して、指定されたリスト内の要素のインデックス位置を見つける方法を学びます。

導入

二分探索は、リスト内の特定の要素を見つけるアルゴリズムです。数千個の要素のリストがあり、特定の要素のインデックス位置を取得する必要があるとします。二分探索アルゴリズムを使用すると、要素のインデックス位置を非常に高速に見つけることができます。

検索アルゴリズムは数多くありますが、その中で最も人気があるのは二分探索です。

二分探索アルゴリズムを適用するには、リスト内の要素を並べ替える必要があります。要素がソートされていない場合は、最初に要素をソートします。

二分探索の概念を理解しましょう。

itn への文字列

二分探索の概念

二分探索アルゴリズムでは、次の方法を使用して要素の位置を見つけることができます。

再帰的方法
反復法

分割統治アプローチ手法の後に再帰的手法が続きます。このメソッドでは、リスト内の要素が見つかるまで、関数自体が何度も呼び出されます。

反復メソッドで要素のインデックス位置を見つけるために、一連のステートメントが複数回繰り返されます。の その間 ループは、このタスクを実行するために使用されます。

二分探索は、各リストのインデックスを検索する必要がないため、線形探索よりも効率的です。二分探索アルゴリズムを実現するには、リストをソートする必要があります。

二分探索を段階的に実装してみましょう。

ソートされた要素のリストがあり、インデックス位置 45 を探しています。

[12、24、32、39、45、50、54]

したがって、リストに 2 つのポインターを設定します。 1 つのポインタは、と呼ばれる小さい値を示すために使用されます。低い 2 番目のポインタは、と呼ばれる最高値を示すために使用されます。高い。

Pythonでタプルを並べ替える

次に、次の値を計算します。 真ん中 配列内の要素。

 mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer)

次に、検索された要素を中間インデックス値と比較します。この場合、 32 に等しくありません 4つ。 したがって、要素を見つけるためにさらに比較を行う必要があります。

検索する数値がmidに等しい場合。それから戻ります半ばそれ以外の場合は、さらなる比較に進みます。

検索する数が 真ん中 数値を比較します n 右側の要素の中央の要素半ばに低く設定します 低 = 中 + 1。

配列スライスJava

それ以外の場合は、 n とともに 中間要素 の左側の要素のうち、半ばそしてセット高いに 高 = 中 - 1。

探している番号が見つかるまで繰り返します。

Python で二分探索を実装する

まず、反復法による二分探索を実装します。一連のステートメントを繰り返し、リストのすべての項目を繰り返します。検索が完了するまで、中間の値を見つけます。

次の反復法のプログラムを理解してみましょう。

Pythonの実装

 # Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let&apos;s understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let&apos;s understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;) </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can&apos;t assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=>

説明：

上記のプログラムでは -

という関数を作成しました。 バイナリ_サーチ() この関数は、ソートするリストと検索する数値の 2 つの引数を取ります。
リスト内の最小値と最大値を格納する 2 つの変数を宣言しました。最低値には初期値 0 が割り当てられます。高いに len(リスト1) - 1、mid は 0 となります。
次に宣言したのは、 その間 という条件でループします。最低に等しいかそれより小さい最高数値がまだ見つからない場合は、while ループが繰り返されます。
while ループでは、中間値を見つけて、インデックス値を検索している数値と比較します。
中間インデックスの値が以下の場合 n 、mid の値を 1 増やしてに割り当てます。検索は左側に移動します。
それ以外の場合は、中間値を減らして、それを高い。検索は右側に移動します。
n が中間値に等しい場合は、戻り値を返します。半ば。
これは次の日まで起こります。低いに等しいかそれより小さい高い。
関数の最後に到達すると、その要素はリストに存在しません。呼び出し元の関数に -1 を返します。

二分探索の再帰的手法を理解しましょう。

再帰的二分探索

二分探索では再帰法が利用できます。ここでは、条件を満たすまで自身を呼び出し続ける再帰関数を定義します。

再帰関数を使用した上記のプログラムを理解してみましょう。

Python プログラム

 # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print(&apos;Element is present at index&apos;, str(res)) else: print(&apos;Element is not present in list1&apos;)

出力：

 Element is present at index 2

説明

上記のプログラムは前のプログラムと似ています。再帰関数とその基本条件を宣言しました。条件は、最低値が最高値以下であることです。

前回のプログラムと同様に中央の数値を計算します。
私たちが使用したのは、もし二分探索を続行するステートメント。
中央の値が探している数値と等しい場合は、中央の値が返されます。
中央の値がその値より小さい場合、再帰関数を探します。 バイナリ_サーチ() 再度、mid の値を 1 つ増やし、low に割り当てます。
中央の値が探している値より大きい場合は、再帰関数が使用されます。 バイナリ_サーチ() 再度、mid の値を 1 つ減らし、low に割り当てます。

最後の部分では、メインプログラムを作成しました。前のプログラムと同じですが、唯一の違いは、 バイナリ_サーチ() 関数。

これは、再帰関数で low、high、mid に初期値を割り当てることができないためです。再帰関数が呼び出されるたびに、これらの変数の値がリセットされます。それは間違った結果をもたらします。

複雑

二分探索アルゴリズムの複雑さは次のとおりです。 ○(1) 最良の場合のために。これは、探している要素が最初の比較で見つかった場合に発生します。の O(ログン) は、二分探索の最悪の平均的なケースの複雑さです。これは、探している要素を見つけるために実行される検索の数によって異なります。

Javaのブール文字列

結論

二分検索アルゴリズムは、リスト内の要素を検索する最も効率的かつ高速な方法です。不要な比較を省略します。名前が示すように、検索は 2 つの部分に分かれています。検索する番号に近いリストの側面に焦点を当てます。

指定された数値のインデックス位置を見つけるための両方の方法について説明しました。

TechCodeview

導入