Change binary search with unknown shift

Question

Suppose I have a sorted array [1,2,3,4,5,6]. I can use binary search to find any number, but what kind of modification in my logical logic should I do. If the sorted array is offset to the left of the unknown number. Like [4,5,6,1,2,3].

Answer 1

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

  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 

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

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

Answer 2

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

Alternatively, you could just do linear sorting at this point, since sorting and searching will take O (n * log (n)). Performing a linear search using brute force will only be O (n).

Answer 3

You only need to execute the usual binary search algorithm once with a modification of the logic regarding the choice of the upper or lower search window. The modification is based on additional comparisons with the first element in the offset array, so you know which segment of the array you are in. You can do this without finding the exact 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 

Conclusion:

 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

In fact, with an unknown change, you can still make binary code, but its arbitrary gain.

One method doubles the size of the ie list:

 [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 part is still ordered.

Now you can view the list before

 list[i-1] > list[i] 

This will be the beginning of the binary search, and at the end of the same amount will be the end of your binary list.

 start = i end = len(list) -1 

Now you can do a binary search

Depending on the average value of the data, it may be lower than O(n)

Method 2

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

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

Method 3

Linear search of all elements

O(n)

Answer 5

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

so let's get started

 l = 0; r = n-1; 

and

 m = (l + r)/2 

if we are looking for v value than:

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

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

(if there is a jump between l and m)

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

than v between l and r, and we can do r = m

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

3) in all other cases, v is somewhere between m and r and we can do l = m

4) repeat for new l and r