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