探索 (Search)
あるデータ集合の中からあるデータを見つける処理を探索もしくは検索という。データ集合はリスト（配列）で表現されることが多い。
探索で知りたいことは：
- データが有るか無いか
- データがどこにあるか
- データが何個あるか
線形探索
検索関数を使用する場合には、ただ要素が見つかったかどうかを知りたいだけではなく、その位置を知りたいことが多い。
関数の処理手順
- 第1引数：検索される数値が入ったリスト（配列）、第2引数：検索する数値
- リスト（配列）の最初の要素から最後の要素まで以下の処理を繰り返す
- リスト（配列）の指定された要素と探している値を比較する
- 値が同じであれば見つかったことになるので、その要素の位置（添え字）を返す
- 見つからなければ添え字ではありえない-1を返す
配列の添え字は0から始まるので、要素が見つかった場合には必ず0以上の値が返される。そこで、その値とは重複しない値、典型的には-1を値が見つからなかった場合に返す位置とする。
def lsearch(num_list, x):
for i in range(len(num_list)):
if num_list[i] == x:
return i
return -1
lst = [20, 42, 45, 47, 44, 40, 15, 36, 6, 11, 50, 16, 29, 7, 1, 25, 31, 39, 38, 14]
v = 16
lsearch(lst, v)値が見つかっていないのにその位置が-1として返されるのは変だと考えるならば、要素が見つからない場合には、Noneを返すようにする方法もある。
def lsearch(num_list, x):
for i in range(len(num_list)):
if num_list[i] == x:
return i
return None
lst = [20, 42, 45, 47, 44, 40, 15, 36, 6, 11, 50, 16, 29, 7, 1, 25, 31, 39, 38, 14]
v = 16
lsearch(lst, v)プログラムの動作テストをするためにはテスト用のデータの作成も重要。
import random
random.sample(range(1, 51), 20)応用問題
最小値の探索
探索値が何個あるかの数え上げ
探索値以上のデータが何個あるかの数え上げ
二分探索
二分探索法は、リスト(配列)で与えられたデータ群の探索領域を段階的に2分割しながら値を探索するアルゴリズム。
線形探索は、検索対象となるリスト（配列）中のデータ群の大小の並びはどのようなものでも構わないが、二分探索では、リスト（配列）中のデータ群の大小の並びは、小さい値のデータから大きいデータ（昇順）、あるいは、大きい値のデータから小さいデータ（降順）に整列されている必要がある。どちらの順で整列させるかは、二分探索の処理法による。
検索対象となる大量のデータ（実世界では100万とか1億単位も一般的）を単純にリスト（配列）にまとめることは難しくはないが、データの値に注目し人手で昇順もしくは降順に順序だててまとめるのは難しい。そこで、データが順序付けされずにまとめられたリスト（配列）を昇順もしくは降順に並べ替える処理が簡単にできるととても役に立つ。このように、データ群を昇順や降順に並べ替える処理が考案されており、その手法は整列(Sort)法と呼ばれる。二分探索の対象となるデータは、この整列法でデータを並べ替えて作られるのが一般的である。整列法に関してはこの次の章で学ぶ。
ここでは、リスト（配列）のデータ群が昇順に整列されているデータを対象とした二分探索法を考える。
def bsearch(num_list, x): # リスト（配列）中のデータは小さいものから順に並べられていること
low = 0 # リスト（配列）の検索領域の下限
high = len(num_list) - 1 # リスト（配列）の検索領域の上限
while low <= high: # 検索領域に要素がある間
mid = (high + low) // 2 # 検索領域の中央の添え字：整数除算を使用
if x > num_list[mid]: # 検索値が中央値より大きい
low = mid + 1 # 検索領域の下限を中央値の添え字より上に再設定
elif x < num_list[mid]: # 検索値が中央値より小さい
high = mid - 1 # 検索領域の上限を中央値の添え字より下に再設定
else: # 大きくも小さくもなければ同じ値なので見つかった
return mid # 添え字を返す
return -1 # 検索値が見つからなかった
lst = list(range(20))
print("lst =", lst)
print("位置 =", bsearch(lst,12))lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
位置 = 12探索過程を見てみましょう。
探索過程が見えるように、処理中の変数の値を表示できるようにします。
def bsearch(num_list, x):
low = 0 # リスト（配列）の検索領域の下限
high = len(num_list) - 1 # リスト（配列）の検索領域の上限
while low <= high: # 検索領域に要素がある間
mid = (high + low) // 2 # 検索領域の中央の添え字：整数除算を使用
print(f'x={x}, mid={mid}:{[num_list[mid]]} low={low}, high={high}, sublist:', num_list[low:high+1])
if x > num_list[mid]: # 検索値が中央値より大きい
low = mid + 1 # 検索領域の下限を中央値の添え字より上に再設定
elif x < num_list[mid]: # 検索値が中央値より小さい
high = mid - 1 # 検索領域の上限を中央値の添え字より下に再設定
else: # 大きくも小さくもなければ同じ値なので見つかった
return mid # 添え字を返す
return -1 # 検索値が見つからなかった
lst = list(range(20))
print("lst =", lst)
print("位置 =", bsearch(lst,12))lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
x=12, mid=9:[9] low=0, high=19, sublist: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
x=12, mid=14:[14] low=10, high=19, sublist: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
x=12, mid=11:[11] low=10, high=13, sublist: [10, 11, 12, 13]
x=12, mid=12:[12] low=12, high=13, sublist: [12, 13]
位置 = 12存在しない値を検索するとどうなるか？
lst = list(range(20))
print("lst =", lst)
print("位置 =", bsearch(lst,30))lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
x=30, mid=9:[9] low=0, high=19, sublist: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
x=30, mid=14:[14] low=10, high=19, sublist: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
x=30, mid=17:[17] low=15, high=19, sublist: [15, 16, 17, 18, 19]
x=30, mid=18:[18] low=18, high=19, sublist: [18, 19]
x=30, mid=19:[19] low=19, high=19, sublist: [19]
位置 = -1