Question

Formatted question description: https://leetcode.ca/all/153.html

Suppose a sorted array 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.

@tag-array

Algorithm

Compare the middle value nums[mid] with the right boundary value nums[right]. If the array is not rotated or the rotation point is in the left half, the middle value must be less than the right boundary value, so go to the left half to continue searching , Otherwise, go to the right half to search, and finally return nums[right].

Code

public class Find_Minimum_in_Rotated_Sorted_Array {

	public class Solution_iteration {
	    public int findMin(int[] nums) {

	        if (nums == null || nums.length == 0) {
	            return 0;
	        }

	        // min is possibly found in 3 cases (eg. 1,2,3,4,5):
	        // 1. min at left half (eg. 5,1,2,3,4)
	        // 2. min at right half (eg. 2,3,4,5,1)
	        // 3. min at mid position (eg. 4,5,1,2,3)


            // 2 cases:
            // 1,2,3,4,5 // @note:@memorize: but this case is included in above if check
            // 2,3,4,5,1

	        int low = 0; // left pointer
	        int high = nums.length - 1; // right pointer

	        /* @note: to restore thinking process
	        while (low <= high) {
	            int mid = low + (high - low) / 2;

	            if (nums[low] < nums[high]) { // meaning not rotated
	                return nums[low];

	            } else if (nums[mid] > nums[low]) { // left part sorted
	                low = mid;

	            } else { // (nums[mid] <= nums[i]) { // right part sorted @note: '=' is crucial
	                // j = mid - 1;
	                high = mid;
	            }
	        }
	        */

	        while (low < high && nums[low] > nums[high]) { // @note: if low < high, then un-rotated, return low

	        	int mid = low + (high - low) / 2;

	        	if (nums[mid] > nums[high]) {
	        		low = mid + 1;
	        	} else {
	        		high = mid; // @note: here, not "high=mid-1"
	        	}

	        	/*
	        	 * @note: below not working, for input [2,1], infinite loop
							why?
							because, if mid>high, then mid is never min, so mid+1
									 if mid<=high, then mid could be max

							in this case, if change the question to be, "find max in rotated sorted array"?
							then, the mid check is the opposite

		        	if (nums[mid] > nums[high]) {
		        		low = mid;
		        	} else {
		        		high = mid - 1;
		        	}

	        	 */
	        }

	        return nums[low];
	    }
	}
}

############

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        if (nums[0] <= nums[n - 1]) {
            return nums[0];
        }
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[0] <= nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

// OJ: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int findMin(vector<int>& A) {
        int L = 0, R = A.size() - 1;
        while (L < R) {
            int M = (L + R) / 2;
            if (A[M] > A[R]) L = M + 1;
            else R = M;
        }
        return A[L];
    }
};

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] <= nums[-1]:
            return nums[0]
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[0] <= nums[mid]:
                left = mid + 1
            else:
                right = mid
        return nums[left]

############

class Solution(object):
  def findMin(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    start, end, mid = 0, len(nums) - 1, 0
    while start + 1 < end:
      mid = start + (end - start) / 2
      if nums[start] <= nums[mid]:
        start = mid
      else:
        end = mid
    return min(nums[0], nums[start], nums[end])

func findMin(nums []int) int {
	n := len(nums)
	if nums[0] <= nums[n-1] {
		return nums[0]
	}
	left, right := 0, n-1
	for left < right {
		mid := (left + right) >> 1
		if nums[0] <= nums[mid] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return nums[left]
}

function findMin(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        const mid = (left + right) >>> 1;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
    const n = nums.length;
    if (nums[0] <= nums[n - 1]) {
        return nums[0];
    }
    let left = 0,
        right = n - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[0] <= nums[mid]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
};

impl Solution {
    pub fn find_min(nums: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = nums.len() - 1;
        while left < right {
            let mid = left + (right - left) / 2;
            if nums[mid] > nums[right] {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        nums[left]
    }
}

153 - Find Minimum in Rotated Sorted Array

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions