binary search algorithm on a circular list
Posted on 2009-04-14
heard this was a google interview question and had need to use it myself.
if i have a circular, sorted list of n values x(0), x(1), x(2), ..... x(n-1) , and given a value u, what is the index that satisfies
x(i) <= u < x(i+1)
iterative searching seems wasteful. i'd use a binary search on this, but how do you handle the circular nature of it? what do you do at the crossovers? are there any c++ algorithms out there that do this?
what would YOU do?