[notes] 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
-104 <= nums[i] <= 104
nums Each value in the unique
Topic data assurance nums Rotated on a previously unknown subscript
-104 <= target <= 104

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/search-in-rotated-sorted-array

        The first thought is to use dichotomy to find . But dichotomy has a very fatal requirement -- That is, the selected area must be orderly . So how to find the above rotation array ？--> still Use dichotomy .

solution ：

        We can find out , Use dichotomy to find the right , Divide a rotation array into 2 after , There must be some Orderly . such as ：[5 6 7 8 0 1 2 3 4]   --> [5 6 7 8 0]  [1 2 3 4] Then continue to divide in no order --> [5 6 7] [8 0] -> [8] [0]...

You can find , There will be a point in order every time , Until it is finally divided into two numbers .

        Then find the orderly , Is it possible to use dichotomy to find ？ The answer is . For example, find 3, Then after the first split , First judge which side is orderly , If it is ordered and satisfies the number found in this region , that , You can compress the region into an ordered one for binary search . If any condition is not met （ Not ordered or within its interval ）, Then repeat the first step , Divide in disorder .

        therefore , We can first distinguish 0 Subscripts and mid Whether the subscript area is orderly , Order goes into this . Judge whether the target value is within , It is no longer located in the disordered area . Otherwise, the second section is orderly , Repeat the above steps , Until the end . Find it and return its subscript . The end of the cycle means that it is not found , return -1.

        Of course, the special case is to pass in an empty array or only one number , Judge alone .

The code is as follows ：

int search(int* nums, int numsSize, int target){
    if (numsSize == 0)
        return -1;
    if (nums[0] == target)
        return 0;
    int begin = 0;
    int end = numsSize - 1;
    while(begin <= end)
    {
        int mid = begin + (end - begin) / 2;
        if (nums[mid] == target)
            return mid;
        if (nums[0] <= nums[mid])
        {
            if (target < nums[mid] && target >= nums[0])
                end = mid - 1;
            else
                begin = mid + 1;
        }
        else
        {
            if (target <= nums[numsSize - 1] && target > nums[mid])
                begin = mid + 1;
            else
                end = mid - 1;
        }
    }
    return -1;
}