Binary search modification

Question

I have been attempting to solve following problem. I have a sequence of positive integer numbers which can be very long (several milions of elements). This sequence can contain "jumps" in the elements values. The aforementioned jump means that two consecutive elements differs each other by more than 1.

Example 01:

1 2 3 4 5 6 7 0

In the above mentioned example the jump occurs between 7 and 0.

I have been looking for some effective algorithm (from time point of view) for finding of the position where this jump occurs. This issue is complicated by the fact that there can be a situation when two jumps are present and one of them is the jump which I am looking for and the other one is a wrap-around which I am not looking for.

Example 02:

9 1 2 3 4 6 7 8

Here the first jump between 9 and 1 is a wrap-around. The second jump between 4 and 6 is the jump which I am looking for.

My idea is to somehow modify the binary search algorithm but I am not sure whether it is possible due to the wrap-around presence. It is worthwhile to say that only two jumps can occur in maximum and between these jumps the elements are sorted. Does anybody have any idea? Thanks in advance for any suggestions.

Answer 1

You cannot find an efficient solution (Efficient meaning not looking at all numbers, O(n)) since you cannot conclude anything about your numbers by looking at less than all. For example if you only look at every second number (still O(n) but better factor) you would miss double jumps like these: 1 5 3. You can and must look at every single number and compare it to it's neighbours. You could split your workload and use a multicore approach but that's about it.

Update

If you have the special case that there is only 1 jump in your list and the rest is sorted (eg. 1 2 3 7 8 9) you can find this jump rather efficiently. You cannot use vanilla binary search since the list might not be sorted fully and you don't know what number you are searching but you could use an abbreviation of the exponential search which bears some resemblance.

We need the following assumptions for this algorithm to work:

• There is only 1 jump (I ignore the "wrap around jump" since it is not technically between any following elements)
• The list is otherwise sorted and it is strictly monotonically increasing

With these assumptions we are now basically searching an interruption in our monotonicity. That means we are searching the case when 2 elements and b have n elements between them but do not fulfil b = a + n. This must be true if there is no jump between the two elements. Now you only need to find elements which do not fulfil this in a nonlinear manner, hence the exponential approach. This pseudocode could be such an algorithm:

let numbers be an array of length n fulfilling our assumptions

start = 0
stepsize = 1
while (start < n-1)
    while (start + stepsize > n)
        stepsize -= 1
    stop = start + stepsize
    while (numbers[stop] != numbers[start] + stepsize)
        // the number must be between start and stop
        if(stepsize == 1)
            // congratiulations the jump is at start to start + 1
            return start
        else
            stepsize /= 2
    start += stepsize
    stepsize *= 2

no jump found