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

Answer 4

Method 1

Actually with an unknown shift you can still do a binary but its kinda wonky.

One method is doubling the size of the list i.e:

[4,5,6,   1,2,3, 4,5,6,   1,2,3]
# basically  mylist.extend(mylist)

As you can see I just doubled the size but the middle section is still ordered.

Now you can go through the list until

list[i-1] > list[i]

This will be you start of the binary search and the same amount at the end would be the end of your binary list.

start = i
end = len(list) -1

Now you can do the binary search

Depending of the data average could be lower then O(n)

Method 2

You can resort the list and do the the binary search:

O(nlog(n)) + log(n)

Method 3

Linear search of all elements

O(n)

Answer 5

Just simple binary search without doubling or sorting or any other preprocessing of array

so lets start

l = 0; 
r = n-1;

and

m = (l + r)/2

if we are searching for value v than:

1) if (there is no jump between l and m)

array[l] < v < array[m] or 

(if there is jump between l and m)

v < array[m] < array[l] or  
array[m] < array[l] < v 

than v is between l and r, and we can make r = m

2) if v is equal to array[l] array[r] or array[m] we found it

3) in all others cases v is somewhere between m and r and we can make l = m

4) repeat for new l and r