【Hot100】33. Search rotation sort array

33. Search rotation sort array
Medium question
However, it is to find a number from an ordered sequence , First reaction Should be 「 Two points 」.
An originally ordered array rotates at a certain point , In fact, it is to divide the original ascending array into two segments .
「 Two points 」 The essence of is two-stage , Not monotonicity . As long as a paragraph satisfies a certain property , Another paragraph does not satisfy a certain property , You can use it 「 Two points 」.
Rotated array , Obviously, the first half meets >= nums[0], The latter half is not satisfied >= nums[0]. We can use this as a basis , adopt 「 Two points 」 Find the rotation point .

class Solution {
    
    public int search(int[] nums, int target) {
    
        // The length of the array 
        int n = nums.length;
        // There are no elements in the array 
        if (n == 0) {
    
            return -1;
        }
        // There is an element in the array 
        if (n == 1) {
    
            return nums[0] == target ? 0 : -1;
        }
        // Define the left and right boundaries of binary search 
        int l = 0, r = n - 1;
        while (l <= r) {
    
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
    
                return mid;
            }

            if (nums[0] <= nums[mid]) {
    
                // If target stay [l,mid] Inner always reduces the right boundary 
                if (nums[0] <= target && target < nums[mid]) {
    
                    r = mid - 1;
                } else {
     // target<nums[0] ,target>nums[mid]  be not in [l,mid] Within the interval , Look to the right 
                    l = mid + 1;
                }
            } else {
     //nums[0] > nums[mid] [5,6,0,1,2,3,4]
                if (nums[mid] < target && target <= nums[n - 1]) {
    
                    l = mid + 1;
                } else {
    
                    r = mid - 1;
                }
            }
        }
        return -1;

    }
}