【アルゴリズム勉強その１】二分探索

この間、paizaでちょろろっと問題を解いた時、ランクAで探索っぽい問題が出た。
組み合わせ数を全部計算すると～京桁になるから工夫しろ、みたいな問題。
正直、全然わからんくて、とりあえず組み合わせ全部作って試させた。
70%は正解だけど、それ以外はタイムオーバー。
たぶん実際にはオーバーフローするやつ。
そこで、そもそもプログラミングとか、アルゴリズムとか、そういうことを勉強しないとダメなのかなーと思い始めた。
どうせ入社するまで暇だし、このまま毎日映画を見たり、トムとジェリーを見返したり、本を読んだり（読もうとすると寝ちゃうので一生読み終わらないフィリップ・ロスの『素晴らしきアメリカ野球』）して過ごすのはいかがなものなので、基本的なアルゴリズムの勉強でもしようと思い立った。
そのメモ。
（あと英語も勉強しないと…）

言語はPython2.7。
いつものように、お気楽～さまでPythonのお勉強する。
お気楽 Python プログラミング入門
いきなり二分探索が出てきたのは、ここに出てきたから(^^)/

二分探索

二分探索 - Wikipedia

高速なデータ探索アルゴリズム
O(log2n)←Ｏが何なのか毎回忘れる
ソート済みじゃないとダメ

アルゴリズム図鑑も持ってるけど、ウィキペディアの例がやたら充実しててわかりやすい

def bsearch(x, ls):
    low = 0 	
    high = len(ls) - 1	
    while low <= high:
	#真ん中を計算，この場合は切り捨て
        middle = (low + high) / 2
        #値を発見したら，探索終了	
        if x == ls[middle]:
            return True
        #真ん中よりも大きければ，真ん中の右側の数値を最小値に*
        elif x > ls[middle]:	
            low = middle + 1
        #真ん中よりも小さければ，真ん中の左側の数値を最大値に
        else:
            high = middle - 1
    #発見できない場合False
    return False