33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

二分搜索，二分后将会形成两个区间，一个区间是顺序的，另一个是无序的。
如果target等于中间值则返回。
分别处理两种情况下移动指针的方式。
当顺序区间在左半边时：
当target在顺序区间内，则更新右指针的位置。
否则更新左指针位置。
当顺序区间在右半边时：
当target在顺序区间内，则更新左指针的位置。
否则更新右指针位置。

class Solution {
    public int search(int[] nums, int target) {

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

        }
        return -1;
    }
}