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
link:{sourcedir}/_0153_FindMinimumInRotatedSortedArray.java[role=include]
最省事的方式当然是遍历,但是,中等难度的题目不可能一个遍历就解决了。
针对有序数组,首先想到的就是二分查找。但是,这里的二分查找有需要做些特别处理。尤其注意的是,选出 mid
后,先去判断它或者它的邻居是否满足条件,满足就直接返回。然后再去调整范围。