Algorithm | 二分探索をPython3で解説（例題あり） - Qiita

二分探索とは 二分探索（バイナリサーチ）とは、かんたんにいうと、数字がソートされたリストのなかから、求めたい数を効率的に求めるための手法である。 例えば、次のようなリストがあったとしよう。 このとき、このリストから7を求めたいとする。 通常は、0から前から順番に見ていって探し出す、という手法をとる。このとき、0, 1, 2,...とみてくので、探すまでに8回の操作が必要である。 しかし、これを二分探索をもちいることでより効率的に値を探し出すことができる。 二分探索は、まず真ん中の値から探索を開始する。このリストであれば、リストの最小値である0と最大値である9を足して2で割った数を真ん中の値midとする。つまり、4の値が取れる。ここで、求めたい値である7がこの値よりも大きいかどうかを判定する。大きければleftに値を入れ、小さければrightに値を代入する。この操作で1回分である。このときは