pythonとアルゴリズムの勉強かねがね、二分探索を実装してみました。
1.ランダムなリストを作成してソートを行う
例:[1,2,4,5,6,9]
2.探索する値を決める
(コードでは、最下部のforループで取りうる範囲の値全てを探索しに行ってます)
例:2
3.リストからド真ん中付近の値を取り出す
リストの長さが偶数の場合→ド真ん中の右側
リストの長さが奇数の場合→ド真ん中
例:[1,2,4,5,6,9]→5
4.リストを3.で取り出した値を境にして二つに分割する
例:[1,2,4,5,6,9]→[1,2,4],[5,6,9]
5.3.で取り出した値を探索する値を比較
一致したら探索終了、不一致なら次へ
例:2 != 5
6.4.で作った2つのリストに対して、左の最大値、右の最小値と探索する値の比較を行う
探索値が左の最大値より小さければ、探索範囲は左に限定できる
探索値が右の最小値より大きければ、探索範囲は右に限定できる
探索値が左の最大値より大きく右の最小値より小さい場合、探索値は存在しないので探索終了
例:左[1,2,4],右[5,6,9]、探索値2
2<4なので探索範囲は左に限定
7.新しく探索範囲とするリストに対して、3.から6.処理を繰り返しを行う
例:[1,2,4]→2
一致したので処理終了
…とこんな感じの探索を二分探索法と呼ぶらしいです。
途中で左側のリストを除外した際、及び正解が導出された時点で左側のリストが存在した場合に、その要素数を加算して「何番目に探索値が存在したか」をチェックできるようにしました。
n個の数列に対して総当たりで探索を行うとnステップの処理が必要になります。
これに対し、二分探索法では1ステップ毎に半分の値を探索対象から除外できるので、n個のデータに対しての処理回数は(log n)回になります。
import copy
import random
# 準備する値の数を入力
numbers = 100
def binary_search(num_list, target):
# 「値が何番目にあるか」を確認するための変数
ans_counter = 0
while True:
# 配列の中心にある値を取り出す
middle = num_list[len(num_list) // 2]
# 配列の左側
left = num_list[:len(num_list) // 2]
# 配列の右側
right = num_list[len(num_list) // 2:]
# 中心の値が探索値と一致したら探索終了(探索値発見)
if middle == target:
ans_counter += len(left) + 1
print("{}は{}番目にありました。".format(target, ans_counter))
break
# 値が最後の1個になっても一致しなかったら探索終了(探索値不存在1)
# 左の最大値 < 探索値 < 右の最小値となった場合探索終了(探索値不存在2)
elif len(num_list) == 1 and num_list[0] != target\
or left[-1] < target < right[0]:
print("{}はありませんでした。".format(target))
break
# 左の最大値より探索値が小さい場合、探索範囲を左側に絞る
elif target <= left[-1]:
num_list = left
# 右の最小値より探索値が大きい場合、探索範囲を右側に絞る
elif right[0] < target:
ans_counter += len(left)
num_list = right
# num_list = list(range(1,numbers+1))
# 重複のない(num_list)個分のデータを作ってソートする
num_list = []
while len(num_list) < numbers:
n = random.randint(1, numbers * 2)
if n not in num_list:
num_list.append(n)
num_list.sort()
print(num_list)
# 乱数の生成される範囲を探索範囲とする
for i in range(1, numbers * 2 + 1):
binary_search(num_list, i)