I am given a sorted array that has been shifted to the right by some amount.
For example [45,61,71,72,73,0,1,21,33,37] ; which is [0,1,21,33,37,45,61,71,72,73] shifted to the right by 5 spaces.
We are also given a target integer that may or may not be in the array. If it is in the array, we are asked to return its index, otherwise -1.
My solution is using iteration to find the breakpoint of the sorted array, i.e. the point where it stops being sorted; in the above example this is at index 4.
Then to apply two binary searches: one to the first half of the array up to the breakpoint, and another one from breakpoint to the end of the array.
My question is, would the time complexity of this be O(log(n)), where n is the number of integers in the array? My understanding is that since we are using two binary searches, this will take a total of O(2 x log(n)) = 0(log(n))
For completeness, I have included my amended code below. To describe it simply, at each 'iteration', I simply found the half of the array that DID NOT contain the break point and did a simple check (comparing the target to the bounds) on whether the target lies in this half; since this half is fully sorted, this is a O(1) operation. Please let me know if this DOES NOT achieve time complexity of O(log(n)) - I believe it does now :)
def shiftedBinarySearch(array, target):
start = 0
end = len(array) - 1
while start < end:
middle = (start + end) // 2
if array[middle] == target:
return middle
else:
#the break lies in the second half of the list
if array[start] < array[middle]:
if target >= array[start] and target < array[middle]:
end = middle
else:
start = middle + 1
#the break lies in the first half of the list
else:
if target > array[middle] and target <= array[end]:
start = middle + 1
else:
end = middle
if start == end:
if array[start] == target:
return start
return -1