C++二进制搜索以查找不动点的索引

Question

我正在实现一个函数，用于查找 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

    vector<int> numbers = {-10, -5, 1, 3, 13, 13, 50, 70};

和

auto temp = find_fixed_point(numbers);
cout << numbers[temp];

它应该给出 3 作为固定点，但只给出 -10 是行不通的。

该算法看起来不错，但它不起作用。有人有想法吗？谢谢，

Answer 1

我认为您的比较运算符用错了方式:

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();
}