LeetCode-153 Find Minimum in Rotated Sorted Array

Title Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

 

The main idea of the topic

An original ordered array is scrambled once, that is, it is divided into two subarrays from one position in the array, and the positions of the two subarrays are interchanged (but the arrangement in the subarray is still maintained), and the smallest number in the disordered array is found.

 

Example

E1

Input: [3,4,5,1,2] 
Output: 1

E2

Input: [4,5,6,7,0,1,2]
Output: 0

 

Solving problems

Based on the improvement of binary search, it is necessary to determine the position of mid (i.e. in the smaller subarray after exchange or in the larger subarray) when binary search is used to query the number direction.

 

Complexity analysis

Time complexity: O(log(n))

Space complexity: O(1)

 

Code

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        
        return solve(nums, 0, n - 1, n);
    }
    //Two points search
    int solve(vector<int>& nums, int low, int high, int n) {
        if(low == high)
            return nums[low];
        int mid = (low + high) / 2;
        // If two boundary pointers are adjacent, it means that the minimum value must be in it, and return the minimum value;
        if(abs(low - high) == 1)
            return min(nums[low], nums[high]);
        //judge mid Specific location of
        if(mid > 0 && mid < n - 1)
            //mid If it happens to be the final answer, just return to the answer
            if(nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])
                return nums[mid];
            else {
                //mid Is in a large subarray
                if(nums[mid] > nums[low] && nums[mid] > nums[high])
                    return solve(nums, mid + 1, high, n);
                //low,mid,high In an ordered array, return low that will do
                else if(nums[mid] > nums[low]) 
                    return nums[low];
                //mid In smaller subarrays
                else
                    return solve(nums, low, mid, n);
            }
        //mid Under the boundary condition, the minimum value must be nearby
        else if(mid > 0)
            return min(nums[mid], nums[mid - 1]);
        else
            return min(nums[mid], nums[mid + 1]);
    }
};

Tags: PHP

Posted on Sun, 03 Nov 2019 12:40:48 -0800 by Hallic7