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
分析: 遇到查询已排序数组第一个应该想到的方法应该是二分法, 时间复杂度低, 运算快.
二分法: 正常版:
时间复杂度
二分查找也称为折半查找, 每次都能将查找区间减半, 这种折半特性的算法时间复杂度为 O(logN).
m 计算
有两种计算中值 m 的方式:
- m = (l + h) / 2
- m = l + (h - l) / 2
l + h 可能出现加法溢出, 最好使用第二种方式.
返回值
循环退出时如果仍然没有查找到 key, 那么表示查找失败. 可以有两种返回值:
-1: 以一个错误码表示没有查找到 key
l: 将 key 插入到 nums 中的正确位置
变种
二分查找可以有很多变种, 变种实现要注意边界值的判断. 例如在一个有重复元素的数组中查找 key 的最左位置的实现如下:
该实现和正常实现有以下不同:
循环条件为 l < h
h 的赋值表达式为 h = m
最后返回 l 而不是 -1
这道题和昨天的 278. First Bad Version (Easy) 都用了变种的方式.
本题解法:
分析: 最小值的位置有三种可能: 最小值在中间, 最小值在左边, 最小值在右边. 如果中间值 < 右边的值. 则最小值在中间或左边, 反之, 在右边. 知道规律后就好写了.
- 4 5 1 2 3
- 5 1 2 3 4
- 3 4 5 1 2
时间复杂度: o(logn) 空间复杂度: o(1)
什么时候用变种什么时候用正常解法呢?
一般来讲, 已知目标数, 查找与目标数相关内容, 则用正常版,
如果需要自己确定目标数, 一般通过巧妙设置 low,mid,high 的值用变种解法做.
来源: http://www.bubuko.com/infodetail-2972352.html