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 could be duplicate elements in the array.

Examples

A = {3, 4, 5, 1, 2}, T = 4, return 1
A = {3, 3, 3, 1, 3}, T = 1, return 3
A = {3, 1, 3, 3, 3}, T = 1, return 1

?Corner Cases

What if A is null or A is of zero length? We should return -1 in this case.

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
      while left < mid and array[left] == array[mid]:
        left += 1
      if array[left] <= array[mid]:
        if array[left] <= target < array[mid]:
          right = mid - 1
        else:
          left = mid + 1
      else:
        if array[mid] < target <= array[right]:
          left = mid + 1
        else:
          right = mid - 1
    if array[left] == target:
      return left
    if array[right] == target:
      return right
    return -1