CONY的世界

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.

其實本來一直很害怕這種題目，今天耐下心來慢慢寫，發現這題也沒想像中難，其實就是清楚分析所有的case

因為想達到O(logN) 的複雜度＋遇到的是有sorting過的array ，所以用二分法來找

不過這題比較麻煩事他有rotation，所以在考慮case的時候要多想一下

首先是base case nums[mid] == target 就 return mid

然後跟extreme case 少到剩下兩個的時候就直接比了

之後才來處理要切的情形

nums[mid] > target 時，target 會在前段的可能case有兩個

1. array 沒有rotation（nums[mid] < nums[end] )

2.array 有rotation (nums[mid] > nums[end] ) 且 nums[end] < target  (這種表示雖然有rotation，但是後半段的值都比target小，所以target還是只會落在前段）  

而nums[mid] < target 也是同樣的思維

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return -1;
        return Findtarget(nums, 0, nums.length-1, target);
    }
    int Findtarget(int[] nums, int start, int end, int target) {
        if(end - start <= 1)
            return (nums[start]==target)?start:(nums[end]==target)?end:-1;
        int mid = (start+end)/2;
        if(nums[mid] == target) return mid;
        if(nums[mid] > target){
            if((nums[mid] <= nums[end]) || (nums[mid] > nums[end] && nums[end] < target))
                return Findtarget(nums,start,mid,target);
            else
                return Findtarget(nums,mid,end,target);
        } else {
            if((nums[start] <= nums[mid]) || (nums[start] > nums[mid] && nums[start] > target))
                return Findtarget(nums,mid,end,target);
            else
                return Findtarget(nums,start,mid,target);
        }
    }
}
另外一個看網路的寫法是利用會有一半是完整ascending 的特性，調整頭尾，一次砍半砍半的做
所以可以看到他先判斷哪一半是ascending，然後確定是ascending那邊，去縮減頭尾
注意只有一個character的狀態，所以判斷上升下降都要有=，然後都要比mid前進or後退，這樣才會不斷縮減範圍而不會無限loop

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