# 0033. Search in Rotated Sorted Array
###### tags: `Leetcode` `Medium` `Binary Search`
## 思路 $O(logN)$
binary search 先计算出最小值的位置rot 判断条件是 **```nums[mid]>nums[end]```**
然后做一个映射，然后正常做binary search
正常binary search 的搜索index 0,1,2,3,...,rot,...N
通过```(mid+rot)%nums.length```做映射之后的index 就可以让原本的0对应到现在的最小值，也就是映射之后就变成了一个递增array
## Code

class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        while(start<end){
            int mid = (start+end)/2;
            if(nums[mid]>nums[end]){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        int rot = start;
        
        start = 0;
        end = nums.length;
        while(start<end){
            int mid = (start+end)/2;
            int realmid = (mid+rot)%nums.length;
            if(nums[realmid]<target){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        if(nums[(start+rot)%nums.length]==target) return (start+rot)%nums.length;
        else return -1;
    }
}

## Code in Java by 笨笨

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len - 1;
        while (left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[left] <= nums[mid]){
                if (nums[left] <= target && target <= nums[mid]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }else {
                if (nums[mid] <= target && target <= nums[right]){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

## 思路
一开始以为很简单，直接扫一遍不就行了。但是没必要，而且没有用到部分有序的性质。合理使用有序可以把时间复杂度降到$O(log(N))$。

如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了。