大家好,我是戴先生
今天给大家介绍一下如何利用玄学二分法找出目标值元素
想直奔主题的可直接看思路2
##题目
整数数组 nums 按升序排列,数组中的值互不相同
在传递给函数之前,nums...在预先未知的某个下标 k(0 数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1...第一个想到的就应该是用二分法试试
下面我们来分析一下
一个增序的数组是这样的
旋转n次之后就是这样的
所以我们的目标就是在这样的数组里边找目标值
可以非常清晰的看到
第二段的所有值都是小于第一段的值...这样思路就非常清晰了
在二分查找的时候可以很容易判断出
当前的中位数是在第一段还是第二段中
最终问题会简化为在一个增序数据中的普通二分查找
我们用数组[1,2,3,4,5,6,7,8,9]举例说明
target...=4的前边
此时,查找就简化为了在增序数据中的查找了
以此类推还有其他四种情况:
mid值在第一段,且在目标值的前边
mid值在第二段,且在目标值的前边
mid值在第二段,且在目标值的后边
mid值就是目标值