Binary search modification on unknown shift

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