[Leetcode]153. Find Minimum in Rotated Sorted Array

怼烎@ 2022-07-12 09:22 157阅读 0赞

Obviously this question can be solved within `O(n)` time by traversing the whole array and looking for the position `i` that satisfies `nums[i] < nums[i - 1]`.  
However, we haven’t make use of the **sorted** feature of the array yet.  
By take **sorted** into consideration, we can use a slightly changed binary search way and reduce the runtime to `O(logn)`.

Noticing that the input array is sorted in ascending order and is rotated.

*  Analyis:  
    
    
    1.  The input array is sorted in ascending order and is rotated, this leads to 2 possible conditions:
    2.  The input array is rotated right k positions where `k % nums.length = 0`. Under this condition, the input array is actually equal to an unroated one. Thus the minimum is the simply the first element.
    3.  The input array is rotated right k positions where `k % nums.length != 0`. Under this conditoion, the input array need to be analysed as following step.
    4.  Under the second condition, the input array is actually sepearted to 2 parts, the minimum element is at position k. Then the 2 parts is `0 - (k - 1)` and `k to (n - 1)`, both in ascending order and satifies equation `nums[0] > nums[nums.length]` and `nums[i] > nums[j]` where `i` belongs to `0 to k - 1` and `j` belongs to `k to n - 1`.
    5.  Thus the algorithm can be described as following.  
        
        
         *  If the array is not rotated or has a length of 1, the first element is the minimum. Otherwise, do following steps.
         *  Set `start = 0`, `end = nums.length - 1`.
         *  Use binary search. `mid = start + (end - start) / 2`.
         *  If mid is located on the left part of the graph, indicating by `nums[mid] > nums[start]`, set `start = mid`.
         *  If mid is located on the right part of the graph, indicating by `nums[mid] < nums[end]`, set `end = mid`.
         *  if `nums[mid] < nums[mid - 1]`, then `nums[mid]` is the minimum.
         *  The stop condition of the binary search is `start < end - 1` since we are using left skewing binary search (i.e. `(start + end) / 2` is always floored to left side). Once the `start` reaches the rightmost position of left part and `end` reaches the leftmost position of the right part, `nums[end]` or `nums[start + 1]` is the minimum. Thus the loop should be terminated.

`O(1)` space and `O(logn)` time. `n` is the length of the input array.

--------------------

The algorithm implementation using Java is showed as following.

public class Solution {
        public int findMin(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
    
            int start = 0;
            int end = nums.length - 1;
    
            if (nums[start] <= nums[end]) { //the array is not rotated, the first element is the smallest
                return nums[start];
            }
    
            while (start < end - 1) {
                int mid = start + (end - start) / 2;
    
                if (mid > 0 && nums[mid] < nums[mid - 1]) {
                    return nums[mid];
                }
    
                if (nums[mid] >= nums[start]) {
                    start = mid;
                }
    
                if (nums[mid] <= nums[end]) {
                    end = mid;
                }
    
            }
    
            return nums[start + 1];
        }
    }