I'm looking for an algorithm similar to binary search but which works with data structures that are circular in nature, like a circular buffer for example. I'm working on a problem which is quite complicated, but I's able to strip it down, so it's easier to describe (and, I hope, easier to find a solution).

Let's say we have got an array of numbers with both its ends connected and an view window which can move forward and backward and which can get a value from the array (it's something like a C iterators which can go forward and backward). One of the values in the array is zero, which is our "sweet point" we want to find.

What we know about values in the array are:

• they are sorted, which means when we move our window forward, the numbers grow (and vice versa),
• they are not evenly spaced: if for example we read "16", it doesn't mean if we go 16 elements backward, we reach zero,
• at last but not least: there is a point in the array where, up to that point values are positive, but after that point they are "flipped over" and start at a negative value (it is something like if we were adding ones to an integer variable until the counter goes around)

The last one is where my first approach to the problem with binary search fails. Also, if I may add, the reading a value operation is expensive, so the less often it is done the better.

PS: I'm looking for C code, but if You know C#, Java, JavaScript or Python and You like to write the algorithm in one of those languages, then it's no problem :).

CodePudding user response：

If I understand correctly, you have an array with random access (if only sequential is alllowed, the problem is trivial; that "window" concept does not seem relevant), holding a sequence of positive then negative numbers with a zero in between, but this sequence is rotated arbitrarily. (Seeing the array as a ring buffer just obscures the reasoning.)

Hence you have three sections, with signs - or - -, and by looking at the extreme elements, you can tell which of the two patterns holds.

Now the bad news: no dichotomic search can work, because whatever the order in which you sample the array, you can always hit elements of the same sign, except in the end (in the extreme case of a single element of opposite sign).

This contrasts with a standard dichotomic case that would correspond to a - or - pattern: hitting two elements of the same sign allows you to discard the whole section in-between.

If the positive and negative subsequences are known to have length at least M, by sampling every M/2 element you will certainly find a change of sign and can start two dichotomies.