алгоритм — бинарный поиск C ++ для поиска индекса с фиксированной точкой
Я реализую функцию, которая находит фиксированную точку, где 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.
Алгоритм выглядит хорошо, но он не работает. У кого-нибудь есть идея? Спасибо,
Решение
Я думаю, у вас просто неправильный способ сравнения:
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();
}
Другие решения
Одним из возможных решений этой проблемы является использование стандартных библиотечных алгоритмов, в данном случае 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 (LOGN) Решение, как и в вашем вопросе, используйте решение для бинарного поиска.
Я согласен с ответом ilent2, проблема в том, что сравнение поменяно местами: >=нет <=,
#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];
}
detector