作者:whisper
链接:http://proprogrammar.com:443/article/624
声明:请尊重原作者的劳动,如需转载请注明出处
本章的目标是解释二分查找的工作原理,识别二分查找的不同方法,并简要介绍 3 种常用的二分查找模板。
在最简单的形式中,二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符,并比较查找目标或将查找条件应用于集合的中间值;如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。如果查以空的一半结束,则无法满足条件,并且无法找到目标。
在接下来的章节中,我们将回顾如何识别二分查找问题,“为什么我们使用二分查找” 这一问题的原因,以及你以前可能不知道的 3 个不同的二分查找模板。由于二分查找是一个常见的面试主题,我们还将练习问题按不同的模板进行分类,以便你可以在实践使用到每一个。
注意:
二进制搜索可以采用许多替代形式,并且可能并不总是直接搜索特定值。有时您希望应用特定条件或规则来确定接下来要搜索的哪一侧(左侧或右侧)。
我们将在接下来的章节中提供一些例子。在这之前,你能自己写一个二分查找算法吗?
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1
提示:
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。
// 想法:使用二分查找
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1, mid;
while(right >= left){
mid = (right+left)/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
基本二分查找问题,左右端点向中间逼近找目标值,mid值是左右端点值和的一半,根据mid位置的值与target值的关系更新right或left,或者返回结果
看其它的解法中mid的求法是这样的mid = left + (right - left) / 2; 加一次除一次不是挺好吗,为什么要减一次除一次加一次呢?
如何识别二分查找?
如前所述,二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时,都应该考虑二分查找。如果集合是无序的,我们可以总是在应用二分查找之前先对其进行排序。
成功的二分查找的 3 个部分
二分查找一般由三个主要部分组成:
预处理 —— 如果集合未排序,则进行排序。
二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
后处理 —— 在剩余空间中确定可行的候选者。
3 个二分查找模板
当我们第一次学会二分查找时,我们可能会挣扎。我们可能会在网上研究数百个二分查找问题,每次我们查看开发人员的代码时,它的实现似乎都略有不同。尽管每个实现在每个步骤中都会将问题空间划分为原来的 1/2,但其中有许多问题:
为什么执行方式略有不同?
开发人员在想什么?
哪种方法更容易?
哪种方法更好?
经过许多次失败的尝试并拉扯掉大量的头发后,我们找到了三个主要的二分查找模板。为了防止脱发,并使新的开发人员更容易学习和理解,我们在接下来的章节中提供了它们。
亲爱的读者:有时间可以点赞评论一下
全部评论