こんにちは。
AtCoderを始めてみたは良いのですが、アルゴリズムを知らないとこれ以上先に進めないなと感じるようになってきました。
（割とPythonの基本的な入出力や条件分岐には慣れることができたのでその点は良いなと思っています。）
ということで、プログラミングコンテストチャレンジブック（通称: 蟻本）を買ってみました。
※友人曰く、かなり完成度の高い本のようです。
ただし、この本は基本的にC++で記載されています。
一瞬、「蟻本はC++で練習してAtCoderもC++で提出しようかな...？」と思ったのですが、今後もPythonでやっていこうと決めました。
なぜかというと、そもそもPythonで作りたいプログラムがあるからです。
もちろんC++でも実装は可能かと思うのですが、機械学習やスクレイピングなどの初心者でも扱いやすそうなライブラリが充実しているのがPythonを選んだ理由だったので...！
ということで、蟻本の内容をPythonで進めています。
自分の理解のため、簡単に記事にまとめようかなというのがこの記事の趣旨です。
二分探索とは？
例えば、あるデータ群の中から条件に一致するデータを探し出したいとします。
この際、全部のデータを最初から一つずつ見ていくのは非効率です。
で、この時に扱うデータが昇順, もしくは降順に並んでいるとすると、真ん中のデータに対してのみ検索すれば効率良いよね？というのが二分探索です。
「ちょうど真ん中のデータが探してるものと一緒か？違うなら大きいか？小さいか？」を把握すれば雑にいうと、一気に検索対象のデータ群を半分のサイズにできるというものです。
図にすると、二分探索ってのはこういうやつです。（絵心よ...！）
前提条件として、数字が昇順, 降順に並んでいる、もしくは並べ直す必要はあります。
既にソート済みのデータを扱う場合や、ソートにかかる計算量を考慮したとしても効率が良くなる場合に有効です。
まぁ大体こういうのはググれば特に実装しなくても使えるように関数が用意されているわけですが、理解のためにPythonにしてみました。
大体以下のようになります。
（間違っていたら教えてください...！）
#n個のデータセットkの中からxを二分探索で探す
def binary_search(x, k, n):
l = 0 #検索範囲の左端
r = n #検索範囲の右端
while r - l >= 1: #検索範囲がなくなったら処理を終了する
i = (l + r) // 2 #iにデータの真ん中の位置を持たせる
if k[i] == x:
return True
elif k[i] < x:
l = i + 1
else:
r = i
else:
return False
てことで、本日は短いですが以上です！
蟻本で言うと、P.26~28あたりの「ハードルがあがったくじびき」の解説あたりの内容をPythonにしてみました。
それではまた〜。