Binary search 33. search rotation sort array

---

Search rotation sort array

for example , [0,1,2,4,5,6,7] In subscript 3 It may turn into [4,5,6,7,0,1,2] .
Here you are. After rotation Array of nums And an integer target , If nums There is a target value in target , Returns its subscript , Otherwise return to -1 .
You have to design a time complexity of O(log n) The algorithm to solve this problem .

Start thinking

It is a more traditional binary search mode

First, you need to split an array every time , It's interesting to know , Our array needs to be divided into two cases .

1. Set the intermediate value nums[mid] and nums[0] Compare the size There are two cases
2. Set the intermediate value nums[mid] and nums[n-1] Compare the size There are two cases

The above division is ok
Can be effectively split
For example, because we mid Writing int mid = l + ((r-l)>>>1); Keep to the left
If you use 1. Set the intermediate value nums[mid] and nums[0] Compare the size ： Need nums[0]<=nums[mid]
If you use 2. Set the intermediate value nums[mid] and nums[n-1] Compare the size ： Need nums[n]<nums[mid]
Take the first case as an example

     public static int search(int[] nums, int target) {
    
        int l = 0 ,n = nums.length-1, r = n;

        while(l<=r){
    
            int mid = l + ((r-l)>>>1);
            if (nums[mid]==target){
    
                return mid;
            }
            if (nums[0] <= nums[mid]) {
    
                if (nums[0] <= target && target < nums[mid]) {
    
                    r = mid - 1;
                } else {
    
                    l = mid + 1;
                }
            } else {
    
                if (nums[mid] < target && target <= nums[n]) {
    
                    l = mid + 1;
                } else {
    
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

Please correct me if there is any mistake