C++で関数のバイナリ検索を実装する方法は？

Question

私は、C + +で、私はコストのかかるサブ問題を抱えています。さらに、このサブ問題bool f(x)は、xの長さが[1、n]から長くなります。 [1、N]の範囲に

、f(k), k < jは常に偽です...とf(m), j < mは常に真ある1<j<n, f(j) = trueような点があります。

私はその点を見つける必要があります。

---

私はそれを行うために必要な方法は、（それもXがNに近い時間がかかる領域に、触れることがないように）x=1から始まるバイナリ検索です。

---

は今のところ、私は手動で私が（偽であるので、f(1)、）関数の最小値で始まり、二分探索実装により強い。次に、f(x) is happy（真）の状態になるまで入力値を2倍にします。この部分は大きな問題ではありません。私はそれを手動でうまくいくことができます。

次に、私は、範囲のバイナリ検索したい[X/2、x]はf(x) = true（f(x/2)がf(1) = false以来、偽等しくなければならない...と私はせずにそれを行う必要があることを指摘し最初値について間違い。そしてこのは物事が少し毛深い取得しているところである。

---

だから私C++はこれがすでに実施していることをはう疑いを持っているが、私はC++に新しいですし、図書館での経験が限られています私は現在バイナリ検索を見ていますが、実際の場所をビンで検索する方法はありませんh関数のすべての値がfalseからtrueに変化します。

むしろ、それは貪欲であると思われます：最初にtrueが見つかるだけで、それは最小値ではなく、trueです。

私はこれをC++でどうやって行いますか？次のように私の検索機能の

---

入力は次のようになります。

f(...)は...

前からブール関数であり、それがどのようなIの性質を持っている必要があります

std::vector<int> range(max); 
for (int j = 0; j < max; j++){ 
    range[j] = j; 
} 

std::some_search_function(range.begin(),range.end(),f(int value)) 

検索中の項目の最初の値から始めて、最も早い項目を返します。f(...)が満足されます。

Answer 1

それを表すインデックスに応じてtrueまたはfalseに "ポイント"するカスタムイテレータを実装し、最初にtrueという値を見つけるためにstd::lower_bound関数を使用できます。