A[i] = i の定点を見つける関数を実装しています。
size_t find_fixed_point(const vector<int>& list)
{
auto lower = list.begin();
auto upper = list.end() - 1;
while (lower < upper)
{
auto mid = lower + (upper-lower)/2;
if ( *mid <= (mid - list.begin()) )
{
// keep searching on left side
upper = mid;
}
else
{
// keep searching on right side
lower = mid + 1;
}
}
return lower - list.begin();
}
これを次のベクトルに適用すると
vector<int> numbers = {-10, -5, 1, 3, 13, 13, 50, 70};
と
auto temp = find_fixed_point(numbers);
cout << numbers[temp];
固定小数点として 3 を与えることになっていますが、-10 を与えるだけでは機能しません。
アルゴリズムは問題ないように見えますが、機能しません。誰にもアイデアがありますか?ありがとう、