Shift Position(Binary Search)

Given 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 of the smallest number.

Assumptions

There are no duplicate elements in the array

Examples

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

class Solution(object):
  def shiftPosition(self, array):
    if len(array) < 1:
      return -1
    left = 0
    right = len(array) - 1
    while left < right - 1:
      mid = (left + right)/2
      if array[mid] < array[mid - 1]:
        return mid
      if array[mid] > array[left] and array[mid] > array[right]:
        left = mid + 1
      else:
        right = mid - 1
    if array[left] < array[right]:
      return left
    else:
      return right