Leetcode_33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 

0 1 2 4 5 6 7

 might become 

4 5 6 7 0 1 2

).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

# 解題思路：

這題和普通的binary search有一點差别。和153的解題思路差不多。但是153更簡單在隻需要找到list中第一個小于最後一個數的數就好了。33這題需要再多讨論幾種情況。

先分兩種情況：

1. nums[start]<nums[mid]

    再讨論，      start<target<mid, end=mid  #這裡省略了nums[]

     or                 t<s,  start-mid

 2. nums[start]>nums[mid]

    再讨論，      mid<target<end, start=mid

    or                 target<mid, end=mid

代碼示例：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start,end=0,len(nums)-1
        while(start<=end):
            mid=start+(end-start)/2
            if nums[mid]==target:
                return mid
            if nums[start]<=nums[mid]:
                if nums[start]<=target and target<=nums[mid]:
                    end=mid-1
                else:
                    start=mid+1
            else:     # start > mid
                if target<=nums[end] and nums[mid]<=target:   # target in [mid,end]
                    start=mid+1
                else:     # target<nums[mid]
                    end=mid-1
        return -1
           

# 代碼用了+1，-1這些倒是無所謂，稍微了解下和解題思路不沖突