33 Search in Rotated Sorted Arrays

两遍binary search 注意写搜索的时候，边界判断条件。还有编写二分搜索的时候，需要多注意边界溢出的问题。二分的边界按照固定的方法来写。

二分搜素需要注意，区间开闭的问题。

Python

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def find_rotate_index(left, right):
            if nums[left] < nums[right]:
                return 0

            while left <= right:
                pivot = (left + right)//2
                if nums[pivot] > nums[pivot + 1]:
                    return pivot + 1
                else:
                    if nums[pivot] < nums[left]:
                        right = pivot - 1
                    else:
                        left = pivot + 1

        def search(left, right):
            while left <= right:
                pivot = (left + right) //2
                if nums[pivot] == target:
                    return pivot
                else:
                    if nums[pivot] < target:
                        left = pivot + 1
                    else:
                        right = pivot - 1
            return -1

        n = len(nums)
        if n == 0:
            return -1
        if n == 1:
            return 0 if nums[0] == target else -1

        rotate_index = find_rotate_index(0, n-1)
        if nums[rotate_index] == target:
            return rotate_index
        else:
            if rotate_index == 0:itn
                return search(0, n - 1)
            if target < nums[0]:
                return search(rotate_index, n - 1)
            return search(0, rotate_index)

Java

class Solution {
    public int subsearch(int[] nums, int left, int right, int target){
        while(left <= right){
            int pivot = left + (right - left)/2;
            if (nums[pivot] == target)
                return pivot;
            else
            {
                if (nums[pivot] < target)
                    left = pivot + 1;
                else
                    right = pivot - 1;
            }
        }
        return -1;
    }
    public int find_rotate_index(int[] nums, int left, int right){
        if(nums[left] < nums[right]){
            return 0;
        }
        while(left <= right){
            int pivot = left + (right - left)/2;
            if (nums[pivot] > nums[pivot + 1])
                return pivot + 1;
            else
            {
                if(nums[pivot] < nums[left])
                    right = pivot - 1;
                else
                    left = pivot + 1;
            }
        }
        return 0;
    }
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0)
            return -1;
        if (n == 1)
            return (nums[0] == target ? 0 : -1);
        int rotate_index = this.find_rotate_index(nums, 0, n - 1);
        if (nums[rotate_index] == target)
            return rotate_index;
        else
        {
            if (rotate_index == 0)
                return this.subsearch(nums, 0, n - 1, target);
            if (target < nums[0])
                return this.subsearch(nums, rotate_index, n - 1, target);
            return this.subsearch(nums, 0, rotate_index - 1, target);
        }
    } 
}