0153 & 0154 Find Minimum in Rotated Sorted Array

Problem Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums, return the minimum element of this array.

Example

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Solution - Unique numbers

The problem wants a code with O(Log(n)) time complexity instead of a trivial O(n) complexity. Obviously, we should consider the binary search to achieve this.

Consider nums[mid] and nums[high], there're would be two cases:

  1. nums[mid]<nums[high]. we are sure that the array is in a ascending order from mid to high. Thus to look for the minimum, we can safely ignore nums[i+1]...nums[high] since nums[mid] is the min of the right half part. We can therefore set high = mid;
  2. nums[mid]>nums[high]. Note that this case should not occur if the array is not rotated, since elements on the right should always be greater than left elements. The only possible case where nums[mid]>nums[high] exists is when minimum of the array is rotated to somewhere in the right part. In this case, we need to look for minimum on the right part: nums[i+1]...nums[high]. Thus we set low = mid+1.

Note that we cannot have the third cases:nums[mid]==nums[high] since numbers in the array is unique and mid = (low+high)/2 never will be equal to high when low<high.

Another point worth to mention is that we are comparing nums[mid] with nums[high] other than nums[low]. This is very important since if we are comparing nums[mid] and nums[low], there will be definitely the third case: nums[mid]==nums[low] when mid==low. For example we have the array: [2,3] or [3,2]. In those case, it's not quite clear how we should do in the code. In addition, even if we have nums[low] < nums[mid], we cannot conclude the minimum is in the right part and simply set low = mid + 1 since nums[low] may be the minimum. All these cases would make the situation complex.

Solution - Duplicate numbers

We also analyze the problem if we allow the duplicate numbers in the array, which is exactly the problem 154 of the LeetCode.

If we follow the logic above, we can clearly note that if duplicate numbers allowed, all else being the same except that we would have the third case:

  • nums[mid]==nums[high].

Note that if this case happens, we cannot determine which side/part of the array we should search in the next. A lazy operation is that since we find two identical numbers, we can safely ignore one of them, that is: high--;. However the drawback is that it will be quite slow, actually in O(n) time complexity if the array is like: [0,1,1,1,1,1,1,1...1].

We can try to improve the time complexity by further decomposing the third case: nums[mid]==nums[high]. If this is the case, we can have a few different cases:

  1. [0,1,1,1,1,1,1,1...1]
  2. [1...1,1,1,1,1,0,1,1]
  3. [1,1,0,1,1,1,1,1...1]

In other words, either the right part or the left part of the array will be all identical. In the first case, we can immediately set high = mid to speed up the algorithm. We can distinguish the case 1 from case 2&3 by examing whether nums[low] is the same as nums[mid], if it is not, then that's the case 1. Otherwise, it must be case 2 or case 3, where we can only do: low++;high--;. But overall, we can improve the efficiency on the case 1 compared to the lazy operation mentioned above.

C++ code - Unique numbers

int findMin(vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        while(low<high){
            int mid = low + (high - low)/2;
            if(nums[mid]<nums[high]) high = mid;
            else low = mid+1;
        }
        return nums[low];
    }

C++ code - Duplicate numbers

 int findMin(vector<int>& nums) { // decomposition of the case 3,  8ms
        int low = 0, high = nums.size() - 1;
        while(low<high){
            int mid = low + (high - low)/2;
            if(nums[mid]<nums[high]) high = mid;
            else if(nums[mid]>nums[high]) low = mid+1;
            else{ // mid == high
                if(nums[low] == nums[mid]) {high--;low++;}
                else high = mid;
            }
        }
        return nums[low];
    }
    /*
    int findMin(vector<int>& nums) { // lazy operation, not fast though: 12ms
        int low = 0, high = nums.size() - 1;
        while(low<high){
            int mid = low + (high - low)/2;
            if(nums[mid]<nums[high]) high = mid;
            else if(nums[mid]>nums[high]) low = mid+1;
            else high --;
        }
        return nums[low];
    }
    */
文章目录