大家好,我是戴先生
今天给大家介绍一下如何利用玄学二分法找出最小值
想直奔主题的可直接看思路2
这次的内容跟 必会算法:在旋转有序的数组中搜索 有类似的地方
都是针对旋转数据的操作
可以放在一块来学习理解...##题目
整数数组 nums 按升序排列,数组中的值互不相同
在传递给函数之前,nums 在预先未知的某个下标 k(0 旋转,使数组变为 [...[4,5,6,7,0,1,2]
关于这段描述还有另外一种容易理解的说法:
将数组第一个元素挪到最后的操作,称之为一次旋转
现将nums进行了若干次旋转
找到数组中的最小值,并返回结果...所以最小值就是在二段的第一个元素
还有一种极端的情况就是
经过多次旋转之后
数组又变成了一个单调递增的数组
此时的最小值就是第一个元素
我们用数组[1,2,3,4,5,6,7,8,9]举例说明
3...也就是最小值存在于mid~end之间
此时问题就简化为了在一个单调递增的区间中查找最小值了
所以总的规律就是:
在二分法的基础上
当中间值mid比起始值start对应的数据大时
判断一下mid和end