大家好,我是戴先生
今天给大家介绍一下如何利用玄学二分法找出目标值元素
想直奔主题的可直接看思路2
##题目
整数数组 nums 按升序排列,数组中的值互不相同
在传递给函数之前,nums...], ..., nums[k-1]](下标 从 0 开始 计数)
例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]
关于这段描述还有另外一种容易理解的说法...:
将数组第一个元素挪到最后的操作,称之为一次旋转
现将nums进行了若干次旋转
给你 旋转后 的数组 nums 和一个整数 target
如果 nums 中存在这个目标值 target
则返回它的下标...这样思路就非常清晰了
在二分查找的时候可以很容易判断出
当前的中位数是在第一段还是第二段中
最终问题会简化为在一个增序数据中的普通二分查找
我们用数组[1,2,3,4,5,6,7,8,9]举例说明
target...所以可以判断出
此时mid=4是处在第一段中的
而且目标值在mid=4的前边
此时,查找就简化为了在增序数据中的查找了
以此类推还有其他四种情况:
mid值在第一段,且在目标值的前边
mid值在第二段