Search rotation sort array

33. Search rotation sort array

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

---

Ideas ： For ordered arrays , The efficiency of binary search is relatively high . And the problem is the rotation of an ordered array , be There is partial order , And binary search is still valid , Just add the conditions of judgment .

• 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 .
• If [mid, r] It's an ordered array , And target The size of [ nums[ mid+1 ], nums[ r ]], We should narrow our search to [mid + 1, r], Otherwise, in the [l, mid - 1] Search for .

Code ：

int search(int* nums, int numsSize, int target){
    
    if(numsSize == 0)
        return -1;
    if(numsSize == 1)
        return nums[0] == target ? 0 : -1;

    int left = 0, right = numsSize - 1;
    while(left <= right)
    {
    
        int mid = (left + right) >> 1;
        if(nums[mid] == target)
            return mid;
        if(nums[mid] >= nums[0]) // Order on the left 
        {
    
            //target In the left ordered interval 
            if(nums[mid] >= target && target >= nums[0])
            {
    
                right = mid - 1;
            }
            //target Not in an ordered interval 
            else
            {
    
                left = mid + 1;
            }
        }
        else // The left side is disordered or partially ordered 
        {
    
            // The right side is orderly and target In the ordered interval on the right 
            if(nums[mid] <= target && target <= nums[numsSize - 1])
            {
    
                left = mid + 1;
            }
            //target Not in the ordered interval on the right 
            else
            {
    
                right = mid - 1;
            }
        }
    }
    return -1;
}