Binary search modification on unknown shift

Question

Suppose I have a sorted array [1, 2, 3, 4, 5, 6]. I can apply binary search to find any number but what modification in my binary search logic I have to do If my sorted array shifted left by some unknown number. Like [4, 5, 6, 1, 2, 3].

Answer 1

1. We can find the shift using binary search. We need to find the first number which is less than the first element of the given array. Something like this:

   def getShift():
       if a[n - 1] > a[0]:
            return 0 // there is no shift
       low = 0 // definitely not less than a[0]
       high = n - 1 // definitely less than a[0]
       while high - low > 1:
           mid = (low + high) / 2
           if a[mid] < a[0]:
               high = mid
           else
               low = mid
       return high
   

2. Now know the shift so we can run standard binary search over two intervals: [0, shift) and [shift, n - 1].

The time complexity is O(log n)(because we run 3 binary searches).

Answer 2

Just re-sort the array after the unknown shift. It will be computationally expensive, but it will be correct.

Additionally, you could also just do a linear sort at this point, since sorting and searching will take O(n*log(n)). Doing a linear search via brute force will only be O(n).

Answer 3

You only need to run through the regular binary search algorithm once, with a modification on the logic as to when to select the upper or lower search window. The modification is based on additional comparisons with the first element in the shifted array so that you know which segment of the array you are in. You can do this without having to actually find the precise location of the split.

In ruby:

LIST = [6,7,8,9,10,1,2,3,4,5]

def binary_search(x)
  first = LIST[0]
  low = 0
  high = LIST.size-1
  while low <= high
    mid = low + (high-low)/2 # avoid overflow
    return mid if x == LIST[mid]
    if (LIST[mid] < first) != (x < first) || LIST[mid] < x
      low = mid + 1
    else
      high = mid - 1
    end
  end
  return -1 # not found
end

1.upto(10) do |x|
  puts "#{x} found at index #{binary_search(x)}"
end

Output:

1 found at index 5
2 found at index 6
3 found at index 7
4 found at index 8
5 found at index 9
6 found at index 0
7 found at index 1
8 found at index 2
9 found at index 3
10 found at index 4