二分探索では項目のコレクションを 2 つに分割して、要素を検出するために必要な直接比較の数を減らしました。ただし、要件が 1 つあります。それは、配列の項目を事前に並べ替える必要があるということです。
二分探索
の 二分探索 メソッドは、特定のリスト メンバーのインデックスを見つけます。これは、最も人気があり、最も高速なアルゴリズムの 1 つです。二分探索手順を実行するには、リスト内のエントリを並べ替える必要があります。
二分探索 要素のインデックスを見つけるためのより効率的な検索手法です。 線形探索 すべてのリストのインデックスを調べる必要がないからです。
二分探索アルゴリズムの動作全体は、次の手順に要約できます。
- ソートされた配列内の中央の要素を見つけます。
- 検索対象の要素と中央の要素を比較します。
- その要素が指定されたリストの中央の要素と等しい場合、中央の要素のインデックスが返されます。それ以外の場合、アルゴリズムは要素を中央の項目と比較します。
- ここで、検索対象の要素がリストの中央の項目より大きい場合、その要素はリストの右半分、つまり中央のインデックス以降の要素と比較されます。
- または、要素がリストの中央の要素より小さい場合は、リストの左半分、つまり中央のインデックスより前の要素のみと比較されます。
再帰的二分探索
二分探索は、ソートされた配列内の要素を検出するために、検索間隔を継続的に 2 つの等しい部分に分割することを意味し、反復二分探索では、完全な二分探索手順をより小さな問題に分割する必要があります。再帰的二分探索は、二分探索に対する再帰的な答えです。
すべて再帰的なソリューションが満たさなければならない特性は次のとおりです。
- 再帰的アプローチには基本ケースが必要です。
- 再帰的アプローチには再帰的テスト ケースが必要です。
- 再帰的アプローチでは、基本ケースに近づける必要があります。
複雑な問題の最下位の細分は、最終ケースである基本ケースによって表されます。したがって、再帰的方法でバイナリ検索を実行するには、アルゴリズムに基本ケースと再帰ケースが含まれており、再帰ケースは基本ケースに進む必要があります。そうしないと、プロセスが完了せず、無限ループが発生します。
二分探索手法を使用すると、並べ替えられた配列内の特定の要素を見つけるのにかかる時間が短縮されます。二分探索法は反復的に実装されることが多いですが、より小さな部分に分割して再帰的に実装することもできます。
コード
#defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!')
出力：
The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list
再帰は、非常に強力なプログラミングおよび問題解決手法です。これを使用して、単純な反復問題から複雑なバックトラッキング問題に至るまで、さまざまなアルゴリズムを評価および実行できます。このチュートリアルでは、Python 言語を使用して再帰二分検索メソッドを作成する方法を検討しました。