c++ - C++ Binary Search 查找固定点的索引

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

Answer 2

#include<iostream>
#include<vector>
using namespace std;

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 if ( *mid < (mid - list.begin()) )
        {   
            // keep searching on right side
            lower = mid + 1;
        }   
        else 
            return mid - list.begin();  
    }   
     return lower - list.begin();
}
int main()
{
    vector<int> numbers = {-10, -5, 1, 3, 13, 13, 50, 70};  
    auto temp = find_fixed_point(numbers);
    cout << numbers[temp];
}

Answer 3

一个可行的解决方案是使用标准库算法，在这种情况下std::find_if()：

int index = 0;
auto result = std::find_if( std::begin( v ) , std::end( v ) , [&]( int value ) { return value == index++; } );

但这里的问题std::find_if()是O(n)，使用简单的线性遍历。

因此，如果您想要一个O(logn)解决方案，就像您的问题一样，请使用您的二进制搜索解决方案。我同意 ilent2 的回答，问题是“交换”比较：应该是>=，不是<=。