最近、並べ替えられたリストで数値を検索するアルゴリズムに遭遇しました。これがその方法です。
与えられた: 与えられた数が検索されている数よりも大きいか小さいかを教えてくれるオラクル。
リストの最初の要素から始めます。1要素先にスキップして、検索されている数より先に進んでいるかどうかをオラクルに尋ねます.
そうでない場合は、2 つの要素をスキップして、行き過ぎたかどうかをオラクルに尋ねます。
4要素先をスキップしない場合など....
検索対象の番号を通過させる最初のスキップが見つかったら、検索対象の番号を含むサブインターバルを特定できます。
最後に、部分区間で二分探索を実行します。
このアルゴリズムの名前を知りたいと思っていたので、さらに調査を行うことができました。
ありがとう
これが、無制限のセットをバイナリ検索する方法です。
たとえばf(n) < t、正の整数の不等式を解くには、f は増加関数です。
具体例:
Solve n**2 + 10*n < 100 over the positive integers.
Let f(n) = n**2 + 10*n for n > 0
f is increasing because it's the sum of increasing functions.
f(1) = 1 + 10 = 11
f(2) = 4 + 20 = 24
f(4) = 16 + 40 = 56
f(8) = 64 + 80 = 144 > 100
Now we binary search the interval [4,8]
f(6) = 36 + 60 = 96
f(7) = 49 + 70 = 119 > 100
Thus n < 7