LeetCode: 153.Find Minimum in Rotated Sorted Array

• tags: LeetCode

解法 1

找到中间节点依次往左右扩散：

1. 向左边扩散，如果左边的大于当前元素，那么当前元素即为最小值
2. 向右边扩散，如果右边的小于当前元素，那么右边元素即为最小值

如果以上不成立则第一个元素为最小元素（未旋转），以下是代码

func findMin(nums []int) int {
	length := len(nums)
	if length == 1 {
		return nums[0]
	}

	// 从中间开始确定方向
	mid := length / 2 - 1

	left, right := mid, mid

	for left - 1 >= 0 || right + 1 < length {
		if left - 1 >= 0 {
			if nums[left - 1] > nums[left] {
				return nums[left];
			}
			left--
		}

		if right + 1 < length {
			if nums[right] > nums[right + 1] {
				return nums[right + 1]
			}

			right++
		}
	}
	return nums[0]
}

优化

参考答案后可通过二分查找做如下优化，首先判断是否被旋转：

• 如果数组尾部的元素大于首部的元素则表示数组未被旋转，可以直接返回第一个元素。
• 由于是从一个有序数组旋转的，所以以上条件可以保证。

然后再判断方向：

• 如果所取中间元素大于数组的第一个元素则最小元素在右边
• 否则最小元素在左边

func findMin(nums []int) int {
	length := len(nums)
	if nums[0] <= nums[length - 1]{
		return nums[0]
	}
	if length == 2 {
		return nums[1]
	}

	left, right := 0, length - 1
	for left < right {
		mid := left + ((right - left) / 2)
		if nums[mid] > nums[mid + 1] {
			return nums[mid + 1]
		}

		if nums[mid - 1] > nums[mid] {
			return nums[mid]
		}

		if nums[mid] > nums[0] {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}