【アルゴリズムの勉強】Pythonで二分探索を書いてみた

学習エントリ。

Pythonで二分探索を実装する。

二分探索ってなんぞ

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量はOlog2nである（O記法）。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。

二分探索 - Wikipedia

# coding: utf-8
import math

example_list = [1,3,4,5,6,7,9,10,13,16,18,22,24,25,26] 
target = 22

def binary_search(list,taget): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)/2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return str(target) + "は見つかりませんでした"
	else:
		return "要素の値が" + str(target) + "のインデックス=>" + str(result)

    
print binary_search(example_list,target) #要素の値が22のインデックス=>11

メモ

・left,rightというリストの両端のインデックスを用意する
・targetの判定によって、centerを用いてどちらかを狭めていく
・targetを見つけたら処理をwhile文を抜ける
・最大まで狭めると処理を終了する
・結果を判定するための変数(result)は-1にしておく。result = 0だとtargetが1(indexが0)の場合に失敗になってしまう。

この前のマージソートのように再帰的に求められるかと思ったが、挫折した。こちらの書き方の方がシンプルで分かりやすい。