有了这个通用公式，再也不怕面试考二分法
大家好，我是戴先生
#前言
二分法是面试中考察频率极高的一个算法
说它简单是因为思路很清晰，就是折半查找对比
说它复杂是因为变形很多，极端情况容易考虑不到
二分法最难的地方其实就是边界的处理
前期对二分法的一些变形做了部分梳理
可以先对比看一下，以便能更好地理解下边的通用公式
今天对二分法做一个总结
分享给大家一个易理解又简单的通用公式
保证从此再也不怕面试考察二分法了
#通用公式
直接上通用公式代码：
public static int searchByBinary(int[] num, int target) {
if (num == null || num.length == 0) {
return -1;
}
int start = 0;
int end = num.length - 1;
int mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (num[mid] == target) {
return mid;
} else if (num[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if (num[start] == target) {
return start;
}
if (num[end] == target) {
return end;
}
return -1;
}注意：
前边也说了，二分法的关键其实就是边界的处理
处理不当就会出现死循环或者越界的问题
写法有很多，但是一般循环条件和循环体里边的赋值方式是需要对应的
比如也有很多写法是（start < end）和start = mid + 1 以及end = mid -1这样的组合
个人认为也可以，但不是太好理解
建议大家也不要贪多，记一种自认为容易理解的边界处理思路就可以了
#公式详解
##01
if (num == null || num.length == 0) {
return -1;
}这部分代码就不用说了
建议大家在平时写代码或者算法题的时候也都养成习惯
一定要先考虑入参为空的情况
##02
int start = 0;
int end = num.length - 1;
int mid;这部分就是常规操作了
拿到查找范围的头和尾
并定义一个中间值变量
##03
while (start + 1 < end) {
// ······
}关于这个循环跳出条件可能就会有很多人疑惑了
一般不是写（start < end）吗？
其实两者的唯一区别就是对边界的处理
前者在start和end相邻的时候是不会进入循环
当出现start和end相邻的时候，二分法的工作其实已经做完了
所以就只需要对这两个值做一个单独对比就行了
也就是下面这段代码
if (num[start] == target) {
return start;
}
if (num[end] == target) {
return end;
}后者在start和end相邻的时候还是会进入while循环
这个时候在循环体内部就要同时对边界也进行统一的处理
比如start = 2，end = 3的情况
此时中间值mid = 2 = start
假如刚好target > num[2]
那么我们就要考虑start与mid的关系了
应该是start = mid + 1?还是start = mid?还是start = mid - 1?
再或者是if条件做单独的判断？
如果是逻辑思维不强的同学，可能就把自己绕晕了
##04
mid = start + (end - start) / 2;这段代码就是取中间值
个人认为这么写更好理解一些
当然这个就因人而异了
按照自己的习惯写mid = （start + end）/ 2也是一样的
##05
if (num[mid] == target) {
return mid;
} else if (num[mid] > target) {
end = mid;
} else {
start = mid;
}这段代码就是跟##03中的循环条件对应的
抛开start和end相邻的情况做的处理
因为绝对存在start ≠ mid ≠ end
所以边界问题的就很好处理了
思路就非常简单清晰了
##06
if (num[start] == target) {
return start;
}
if (num[end] == target) {
return end;
}这部分代码就是对边界进行单独处理
循环体内只需要做通用的处理就行
边界问题单独处理更容易理解一些
##07
return -1;如果到了这一步就是没有没有目标值
直接返回特定值就行了
#举个栗子
接下来我们使用一些极端例子来考验一下这个通用公式
因为所有的例子最终都会简化成下边的极端情况
##极端情况01
int[] num = {1};
int target = 1;此时代码根部就不会进入while循环
直接会走到对边界处理的代码
直接就返回结果index = 0
##极端情况02
int[] num = {1, 2};
int target = 1;同样的，此时代码根部就不会进入while循环
直接会走到对边界处理的代码
直接就返回结果index = 0
##极端情况03
int[] num = {1, 2, 3};
int target = 1;此时start = 0；end = 2
进入while循环后mid = 1
而num[mid = 1] = 2 > target = 1;
所以start = mid = 1
此时start = 1；end = 2
将不会进入循环，问题简化为##极端情况02
文/戴先生@2022年09月17日
腾讯云开发者
