33.md

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.

my thoughts:

1. if the sorted array is rotated, then the first n > last n. the array will increase to max n and suddendly drop to the min n and then keep increaing till the end.
step 1. find the idx of the max. idx of the min is the next one.
step 2. compare target with the start, end, min and max. 
		if it is some where between end and start, return -1
		if it > max or < min, return -1
		if it > start, two pointer first half (till max)
		if it < end, two pointer second half (from min)

my solution:

**********40 ms
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        length = len(nums)
        start = nums[0]
        end = nums[-1]
        if start == end:
            if start == target:
                return 0
            return -1
        if start<end:
            l = 0
            r = length -1
            while l<r:
                if nums[(l+r)/2]==target:
                    return (l+r)/2
                elif nums[(l+r)/2]<target:
                    l = (l+r)/2+1
                else:
                    r = (l+r)/2-1
            if nums[l] == target:
                return l
            return -1
        p1 = 0
        p2 = length - 1
        mid = (p1+p2)/2
        while nums[mid]<nums[mid+1]:
            if nums[mid]>=start:
                p1 = mid
            if nums[mid]<=end:
                p2 = mid
            mid = (p1+p2)/2
        if target > nums[mid] or target < nums[mid+1]:
            return -1
        if target < start and target > end:
            return -1
        if target >= start:
            l = 0
            r = mid
        if target <= end:
            l = mid+1
            r = length - 1
        while l<r:
            if nums[(l+r)/2]==target:
                return (l+r)/2
            elif nums[(l+r)/2]<target:
                l = (l+r)/2+1
            else:
                r = (l+r)/2-1
        if nums[l] == target:
                return l
        return -1

my comments:

from other ppl's solution:

1. bravo one pass binary search, 29ms:
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        hi, lo = len(nums)-1, 0
        
        while lo <= hi:
            mid = (hi + lo)//2
            if nums[mid] == target: return mid
            
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid
        return -1