Rotated sorted array

1. What is? Rotated Sorted Array

stay leetcode In related topics , Yes Rotated Sorted Array The relevant definition is ：
An array of integers nums In ascending order , The values in the array are 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] .

informally , There are no equal values in the rotation array , And the array can be divided into two consecutive parts , The two parts are arranged in ascending order .

2. Look for the minimum value in the rotation sort array

leetcode in 153 topic , Is to find the minimum value in the rotation array .
An ascending array that does not contain repeating elements is rotated , You can get the following visual line chart ：

It's not hard to see from the picture , Suppose the last element in the array is x, Then the elements to the right of the minimum must be smaller than this element , The left element of the minimum value is larger than this value .

When performing binary search , Suppose the left and right boundaries are low, high, In the middle pivot.

1. nums[pivot] < nums[high], explain nums[pivot] Is the element to the right of the minimum , So ignore the right half of the binary search .
   
   2.nums[pivot] > nums[high], explain nums[pivot] Is the element to the left of the minimum , So ignore the left half of the binary search .
   
   Because the array elements are not repeated , As long as the current interval length is not 1,pivot Not with high coincidence . And when the interval length is 1 when , This indicates that the binary search has ended .

int run() {
    int nums[] = {4,5,6,7,0,1,2};
    int n = sizeof(nums)/ sizeof(nums[0]);
    int left = 0, right = n - 1;
    while(left < right) {
        int pivot = (left + right) / 2;
        if (nums[pivot] < nums[right]) {
            right = pivot;
        } else {
            left = pivot + 1;
        }
    }
    return nums[left];
}

Note that when the above code terminates ,right It happens to be with left equal .

3. Search rotation sort array

A similar question is leetcode 33 topic , Search in a rotationally sorted array .

The solution is similar to the above , First, find the minimum point , You can divide the data into two ordered parts , And then look nums[0] And target Size . If nums[0]<target, Explain that you want to perform a binary search in the left half . On the contrary, binary search is performed in the right half .

int run2() {
    int nums[] = {4,5,6,7,0,1,2};
    int n = sizeof(nums)/sizeof(nums[0])-1;
    int left = 0, right = n-1, target = 0;
    while(left < right) {
        int pivot = (left + right) / 2;
        if (nums[pivot] < nums[right]) {
            right = pivot;
        } else {
            left = pivot + 1;
        }
    }
    
    int curleft = 0, curright = 0;
    if (nums[0] < target) {
        curleft = 0, curright = left - 1;
    } else {
        curleft = left, curright = n-1;
    }
    while(curleft <= curright) {
        int mid = (curleft + curright) / 2;
        if (nums[mid] < target) {
            curleft = mid + 1;
        } else if (nums[mid] > target) {
            curright = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}