[leetcode] 33. Search rotation sort array

33、 Search rotation sort array

subject ：

An array of integers nums In ascending order , The values in the array Different from each other .

Before passing it to a function ,nums In some unknown subscript k（0 <= k < nums.length） On the rotate , Make array [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] （ Subscript from 0 Start Count ）.

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 .

Example 1：

 Input ：nums = [4,5,6,7,0,1,2], target = 0
 Output ：4

Example 2：

 Input ：nums = [4,5,6,7,0,1,2], target = 3
 Output ：-1

Example 3：

 Input ：nums = [1], target = 0
 Output ：-1

Tips ：

1 <= nums.length <= 5000
-10^ 4 <= nums[i] <= 10^4
nums Each value in the unique
Topic data assurance nums Rotated on a previously unknown subscript
-10^ 4 <= target <= 10^4

Their thinking ：

For ordered arrays , You can use the binary search method to find elements .

What we can find is that , When we split the array from the middle into left and right parts , There must be a part of the array that is ordered . Take for example , We from 6 After this position is separated, the array becomes [4, 5, 6] and [7, 0, 1, 2] Two parts , And the left side of it [4, 5, 6] The array of this part is ordered , So are others .

This suggests that we can view the current mid Two parts separated for the location of the partition [l, mid] and [mid + 1, r] Which part is orderly , And determine how we should change the upper and lower bounds of the binary search according to the ordered part , Because we can tell from the ordered part that target In not in this part ：

If [l, mid - 1] It's an ordered array , And target The size of [nums[l],nums[mid]), We should narrow our search to [l, mid - 1], Otherwise, in the [mid + 1, r] Search for .

It should be noted that , There are many ways to write dichotomy , So in judgment target There may be differences in detail when the relationship between size and ordered parts .

class Solution {
    
    public int search(int[] nums, int target) {
    
        int n = nums.length;
        if (n == 0) {
    
            return -1;
        }
        if (n == 1) {
    
            return nums[0] == target ? 0 : -1;
        }
        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 (nums[0] <= target && target < nums[mid]) {
    
                    r = mid - 1;
                } else {
    
                    l = mid + 1;
                }
            } else {
    
                if (nums[mid] < target && target <= nums[n - 1]) {
    
                    l = mid + 1;
                } else {
    
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}