Given a target integer T and an integer array A, A is sorted in ascending order first, then shifted by an arbitrary number of positions.
For Example, A = {3, 4, 5, 1, 2} (shifted left by 2 positions). Find the index i such that A[i] == T or return -1 if there is no such index.
Assumptions:
There are no duplicate elements in the array.
Examples:
A = {3, 4, 5, 1, 2}, T = 4, return 1
A = {1, 2, 3, 4, 5}, T = 4, return 3
A = {3, 5, 6, 1, 2}, T = 4, return -1
class Solution(object):
def search(self, array, target):
if len(array) < 1:
return -1
left = 0
right = len(array) - 1
while left < right - 1:
mid = (left + right)/2
if array[mid] == target:
return mid
if array[mid] >= array[left]:
if array[mid] > target and array[left] <= target:
right = mid - 1
else:
left = mid + 1
elif array[mid] < array[left]:
if array[mid] < target and array[right] >= target:
left = mid + 1
else:
right = mid - 1
if array[left] == target:
return left
if array[right] == target:
return right
return -1
