4
153. 寻找旋转排序数组中的最小值
source link: https://segmentfault.com/a/1190000040033368
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
153. 寻找旋转排序数组中的最小值
实际在考察二分查找的方法
double 转 int,是直接舍去小数。
正数:
向上取整或者向下取整或四舍五入
Math.ceil(),Math.floor(),Math.round()
旋转后的数列会出现以下两种情况:
- while循环只能选择Left和Right的原因
判断条件只能选p和Right的原因(红框为条件,蓝框为选择结果)
- p>R,只有pR这一种选择;
- p<R,有这两种情况,判断后的操作都是选择互补段Lp
- 而对于p>L,有两种情况,判断后的操作第一个选pR段,第二个选Lp段,无法区分
- p<L只有一种Lp情况。
选择好某一段,应该是L = p + 1,而不是R = R - 1 的原因
- p>R,p必定在最大值及往前,所以L=p+1,要么nums[p+1]=最小值,要么在最小值往前。选pR段,R不变。
- p<R,p必定在最小值及往后,所以R=p,当nums[p]=最小值时,R=p-1就会跳过最小值。选Lp段,L不变。
- 最终返回 p L R都行
官方:
直接else
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK