0

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 を与えるだけでは機能しません。

アルゴリズムは問題ないように見えますが、機能しません。誰にもアイデアがありますか？ありがとう、

4

3 に答える 3

2

間違った方法で比較演算子を使用していると思います：

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();
}
于 2013-08-24T09:27:02.807 に答える