二分法 - 知識メモ

メモだけ

N 個のデータの中から a なる値をもつデータを探したい

（１）データをソート（クイックソート等）（O(logN)）
（２）真ん中の値 b が a より大きいか小さいか見る
（３）b < a なら b より大きい列に対して同じように、a と真ん中の値とを比べる。b > a でも同様

これで O(log_2 N) オーダーで探せる

詳しく学ぶならニュートン法とかも調べよう