Saturday, 24 August 2013

C++ Binary Search to find the index of fixed point

C++ Binary Search to find the index of fixed point

I am implementing a function that finds a fixed point where 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();
}
so if I apply this to the following vector
vector<int> numbers = {-10, -5, 1, 3, 13, 13, 50, 70};
and
auto temp = find_fixed_point(numbers);
cout << numbers[temp];
It is supposed to give 3 as fixed point but it does not work just giving
me -10.
The algorithm looks okay but it does not work. Anybody has an idea? Thanks,

No comments:

Post a Comment