正しく実装するのが実は難しい二分探索

この前から珠玉のプログラミングっていう本を読んでて「なるほどな」っと思うことがあったのでまとめてみる

まず、二分探索って結構簡単に実装出来そうな雰囲気あるし

線形探索（先頭から一個ずつ探索する方法）よりも効率的な部分がある（大抵は線形探索でも十分間に合うし速度も問題ない）

それは線形探索がO(n/2)に対して二分探索はO(log n)で探索が可能だから

ただ要素数がある程度少ない場合は線形探索の方が良くて

むしろ無理に二分探索を実装するとバグの原因になったりするし

そもそもデータ構造と二分探索の探索法の関係でデータがソートされている必要がある

ここまでの前提を踏まえて

二分探索を考えてみると、すこしまずい書き方がある

例えばlow,highがあるとして

middleという二分探索で探索する集団の中央値をmiddle = (low+high)/2と定義してしまうことである

このように定義してしまうと6/2も7/2も結果として3になってしまう

特に要素がどう並んでいるか、どのような成分を持つかわからない時はこういう誤差を捨ててしまう処理はエラー、バグの原因になる

なので、high,low,middleと言った基準点を詳細な<,==,>といった比較で判別する必要がある

こういった細かいことを踏まえて

二分探索を正しく書くのは実は難しい