033._search_in_rotated_sorted_array.md

###33. Search in Rotated Sorted Array

题目: https://leetcode.com/problems/search-in-rotated-sorted-array/

难度: Medium

思路：

最直观的是O(N)解法

but tag是binary search，应该和find min in rotated array类似。 判断是否有序，然后做二分。 最容易理解的写法

• 如果是mid，return mid
• 左边有序，判断是否在左边，否则在右边中寻找
• 右边有序，判断是否在右边，否则在左边寻找
• 都没找到，return -1

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l,r = 0, len(nums) - 1

        while l <= r :
        	mid = (l+r)/2
        	if target == nums[mid]:
        		return mid
        	if nums[mid] < nums[r]:
        		if nums[mid] < target <= nums[r]:
        			l = mid + 1
        		else:
        			r = mid - 1
        	else:
        		if nums[l] <= target < nums[mid]:
        			r = mid - 1
        		else: 
        			l = mid + 1
        return -1