LC.33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/description/
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.

time: o(logn) space: o(1)

与Find Minimum in Rotated Sorted Array类似。因为rotate, 所以不能直接用Binary Search, 需要进行 二次判定。

case 1: nums[mid] == target, return mid.

case 2: nums[mid] < nums[r]. 此时说明 右侧是正常升序，没有rotation, 若是这种情况下 target > nums[mid] && target <= nums[r] 就在右侧查找，其他情况左侧查找。

case 3: nums[mid] > nums[r]. 此时说明 左侧是正常升序，没有rotation, 若是这种情况下 target < nums[mid] && target >= nums[l] 就在左侧查找，其他情况右侧查找

note here since there is no duplicate and the left + 1 = mid will exit, there wouldnt be a case that the nums[left]= nums[mid] or nums[mid] == num[right]
make sure also checks the LC.81

public int search(int[] nums, int target) {
        if (nums == null || nums.length ==0 ) return -1 ;
        int left = 0, right = nums.length -1 ;
        while(left + 1 < right){
            int mid = left + (right-left)/2;
            if (nums[mid] == target) return mid ;
            //break into two parts: note, there is no duplicate
            //first half
            if (nums[left]< nums[mid] ){
                if (target<=nums[mid] && nums[left] <=target){
                    right = mid ;
                }else {
                    left = mid ;
                }
            }
            //second half:注意判断顺序进行改变
            else if (nums[mid] < nums[right]){
                if (nums[mid]<=target && target <= nums[right]){
                    left = mid ;
                }else {
                    right = mid;
                }
            }
        }
        //post processing for the left and right
        if (nums[left] == target){
            return left ;
        }
        if(nums[right] == target){
            return right;
        }
        return -1 ;
    }