153. Find Minimum in Rotated Sorted Array #

Problem #

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.

Example 1:

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

Example 2:

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

Problem Summary #

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (For example, the array [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.

Solution Approach #

Given an array originally sorted in ascending order, but at some split point, the two parts after splitting the array are swapped, placing the larger values at the front of the array. Find the minimum element in this array.
Finding the minimum element of the array is essentially finding the split point: the previous number is greater than the current number, and the next number is also greater than the current number. Binary search can be used to search the two ordered intervals that need to be searched. The time complexity is O(log n). This problem can also be solved by brute force: traverse from the beginning and dynamically maintain a minimum value, with time complexity O(n).

Code #


package leetcode

// Solution 1: Binary search
func findMin(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		if nums[low] < nums[high] {
			return nums[low]
		}
		mid := low + (high-low)>>1
		if nums[mid] >= nums[low] {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return nums[low]
}

// Solution 2: Binary search
func findMin1(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	if nums[len(nums)-1] > nums[0] {
		return nums[0]
	}
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[low] < nums[high] {
			return nums[low]
		}
		if (mid == len(nums)-1 && nums[mid-1] > nums[mid]) || (mid < len(nums)-1 && mid > 0 && nums[mid-1] > nums[mid] && nums[mid] < nums[mid+1]) {
			return nums[mid]
		}
		if nums[mid] > nums[low] && nums[low] > nums[high] { // mid is in the part with larger values
			low = mid + 1
		} else if nums[mid] < nums[low] && nums[low] > nums[high] { // mid is in the part with smaller values
			high = mid - 1
		} else {
			if nums[low] == nums[mid] {
				low++
			}
			if nums[high] == nums[mid] {
				high--
			}
		}
	}
	return -1
}

// Solution 3: Brute force
func findMin2(nums []int) int {
	min := nums[0]
	for _, num := range nums[1:] {
		if min > num {
			min = num
		}
	}
	return min
}