153. Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
二分搜索,寻找断裂点。
当left小于right时循环。
每次计算出mid,分为两种情况:
- 如果nums[mid]小于nums[nums.length-1],则右半侧为顺序的。
- 反之则左半侧为顺序,右半侧为无序的。
以此来更新搜索范围。
由于mid计算公式向下取整。
当更新left时更新为mid+1,向前一格。
当更新right时更新为mid。
最后返回nums[left]。
1 | class Solution { |