この記事では、再帰を使ってバイナリサーチを実装する方法を理解します。
バイナリサーチとリカージョンについては、もうお分かりかと思います。
この記事では、バイナリサーチと再帰を簡単に説明します。
この記事もチェック：Pythonによるバイナリサーチ(二分探索)をwhile文を使って実装する
バイナリサーチとは
バイナリサーチは、並べ替えられた要素のリストの中から要素を見つけるための効率的で高速なアルゴリズムです。
配列を半分に分割することを繰り返して要素を見つけ、分割の真ん中を比較して、どの分割に要素が存在する可能性があるかを特定します。
バイナリサーチを実装するためには、下限ポインタ、上限ポインタ、中間ポインタの3つのポインタが必要です。
サブ配列の分割は下界と上界で定義し、中間ポインタの値は位置を特定する必要がある要素の値と比較します。
バイナリサーチの詳細についてはこちらをご覧ください。
再帰性とは？
さて、バイナリサーチは様々な方法で実装することができますが、そのいくつかを以下に紹介します。
- ループを用いた二項探索アルゴリズム
-
- バイナリサーチツリーを用いたバイナリサーチ アルゴリズム
この記事では、再帰を使ってバイナリサーチを実装することにします。
ある関数が、より大きな問題の同じタイプの小さな問題を解決するために、それ自体を直接または間接的に呼び出す場合、このテクニックは再帰として知られています。
再帰の詳細については、こちらをご覧ください。
再帰を用いた二項探索の実装
ここでは、Pythonで再帰を使ったバイナリサーチのアルゴリズムを実装してみましょう。
各行が何を行っているのか理解しやすいように、コメント付きでコードを追加しています。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def Binary_Search(arr,n,lb,ub,X):
# 1. List is empty
if(n==0):
print("ERROR!")
# 2. If element is not found lb exceeds ub
elif(lb>ub):
print("Not found!")
# 3. Keep searching for the element in array
else:
mid = int((lb+ub)/2)
if(arr[mid]==X):
print(mid+1)
elif(arr[mid]>X):
Binary_Search(arr,n,lb,mid,X);
elif(arr[mid]<X):
Binary_Search(arr,n,mid+1,ub,X);
arr = [1,2,3,4,5,6,7,8,9]
n = len(arr)
X = int(input())
Binary_Search(arr,n,0,n-1,X)
|
この記事もチェック：Pythonによる線形探索の実装をコードを交えて分かりやすく解説する
Outputs
Fake Tags
Fake tag
—Fake tag
まとめ
この記事では、バイナリサーチと再帰の基礎知識とともに、再帰を使ってバイナリサーチを実装する方法について理解しました。
このチュートリアルを気に入っていただければ幸いです。
お読みいただきありがとうございました。
このようなチュートリアルをもっと見るために滞在してください