Quick method for search a value in a (sorted) circular data structure

user_9068493 0
Viewed 102

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 :).

search algorithm c++
2 Answers

If I understand correctly, you have an array with random access (if only sequential is allowed, 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.

user_11965490

You can solve your problem using a galloping (exponential) search.

For simplicity I assume there are no duplicate items.

Start from the back and progress to the left in direction of smaller values. You begin with a jump of one index to the left, each next jump is exponentially bigger. With each jump to the left you should find a smaller value. If you encounter a greater value that means that zero is somewhere between the last two visited indexes. The only case when you will never encounter a greater value is when the zero is exactly at the beginning of the array.

After the jump from index i to i-j that jumped over zero, you've got a range in which zero resides. Since the jump was too far, try jumping from i to i-j/2. If that's still too far (overjumped zero) you try i-j/4 and so on. So this time each jump tried is exponentially smaller. With each step you divide the possible range where zero resides by half. On the other hand, if i-j is too far, but i-j/2 is too near (not reached zero yet), you try i-j/2-j/4. I hope you get the idea now.

This has O(lg n) complexity.

user_8214970
Related