二分查找（搜索）的英文名是 Binary Search，直译过来其实应该叫二进制搜索，但这些都不重要，只要知道有这么个英文名就行。
什么是二分查找
二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们需要在应用二分查找之前先对其进行排序。
二分查找是计算机科学中最基本、最有用的算法之一。 它描述了在有序集合中搜索特定值的过程。二分查找中使用的术语有：
- 目标 Target —— 你要查找的值
- 索引 Index —— 你要查找的当前位置
- 左、右指示符 Left，Right —— 我们用来维持查找空间的指标
- 中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引
二分的本质
我们平时所说的二分大多指数组的二分，因为数组可以随机访问嘛；
不过这种二分实在太狭义了，二分的本质是将问题规模缩小到一半，因此二分和数据结构没有本质关系！
但不同的数据结构却给二分赋予了不同的色彩；
比如：
跳表就是链表的二分（比如redis的跳跃表）；
二叉搜索树就是树的二分；
……；
二分查找的三个基本组成部分
二分查找的先决条件是【有序的折半逻辑】，即每次折半查询时，有条件区分出另一半数据，不一定非得是数学上的升序降序；二分查找一般由三个主要部分组成：
- 预处理 —— 如果集合未排序，则进行排序。
- 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
- 后处理 —— 在剩余空间中确定可行的候选者。
二分查找的三种基本模板
模板-I-1
- 一般用于精确查找值;
- 结束条件：L>R;
while ($L <= $R) {
$mid=$L+floor(($R-$L)/2);//防止溢出
if ($mid < $target) {
$L = $mid+1;
} else if ($mid > $target) {
$R = $mid-1;
} else if ($mid == $target) {
return $mid; //注意，此模板一般直接返回结果
}
}
return null;
模板-II-2
- 一般用于寻找左边界；
- 结束条件：L==R；
while ($L < $R) {
$mid=$L+floor(($R-$L)/2);//防止溢出
if ($mid < $target) {
$L = $mid+1;
} else if ($mid >= $target) {
$R = $mid; //注意此处R=mid
}
}
return $R;//L或R都行，因为结束条件是L==R;
模板-III
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
模板 #3 是二分查找的另一种独特形式：
它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
模板-III 的边界条件
- 初始条件：left = 0, right = length-1
- 终止：left + 1 == right
- 向左查找：right = mid
- 向右查找：left = mid
透过小白兔(鼠)试毒问题去看二分的本质
尽管上面已经说了, 不要将二分法局限于某种数据结构, 但多数人还是习惯于狭义的将二分法理解为数组的二分, 总觉着问题得能具象化为一组数才可以施展二分大法。
实则不然, 上面提到过, 二分的本质在于将问题规模缩小到原来的一半, 所以请看下面这道题：
现在有1000瓶药水, 其中1瓶是毒药, 只需一滴就可让小白兔在24小时内死亡; 问，如何在最短时间内用最少的小白兔, 找出这瓶毒药？
该题据说是某大(鹅)厂面试题, 看上去似乎挺简单:
1000只小兔子, 挨个儿试; 或者, 1只兔子, 一天试一瓶;
不过嘛, 想想也知道答案不是这样, 要不, 就没有考你的必要了。
那么，如何巧妙的找到这瓶毒药呢？
这就要用到本文一直在讲的二分法了；乍一看，这题貌似和二分扯不上关系，如果我们把题目简化一下，就好理解了。
现在有4瓶药水, 其中1瓶是毒药, 只需一滴就可让小白兔在24小时内死亡; 问，如何在最短时间内用最少的小白兔, 找出这瓶毒药？
先套用上面的简单解法：4只小兔子，或者1只试4天；
发散你的小思维再想一想，能否再缩短一些？
实际上，这个简单方案，用不到4只或4天，只需3只或3天即可，因为最后一瓶可以用排除法得到答案；
所以，问题就可以继续简化为：
现在有3瓶药水, 毒药可能在里边也可能不在，如何用最小的代价确定它在不在里边。
接下来该如何优化这个解法呢，也就是，如何把3瓶不相干的药水二分呢？
如果你没有思路，就想想二分法的英文名，它为什么叫 Binary Search？
其实就是将数字转化为二进制吖！聪明的你是不是也想到了呢？
现在我们将 1到3号瓶 按二进制进行编号：
01 - 1号瓶
10 - 2号瓶
11 - 3号瓶
它们的共性是什么，也就一目了然了，每一个数都由两位二进制数构成，如果我们把问题分成这么两类来看：
1、有毒药水的第1位是否为1；
2、有毒药水的第2位是否为1；
是不是就可以借用二分思路了呢？
根据这个思路，需要请来两只小兔子奉献一下，将其编号为1号兔和2号兔，并将3瓶药水按上面的二进制表达式编号：
1号兔只喂二进制第一位是1的药水；
2号兔只喂二进制第二位是1的药水；
24小时后，如果：
1号兔死亡，说明有毒的是3瓶中的第1瓶；
2号兔死亡，说明有毒的是3瓶中的第2瓶；
如果1号和2号都没事儿，说明有毒的是被我们抛弃的那一瓶；为了便于统一观察，可以将被抛弃的那瓶药水的二进制编号为 00，转换为十进制即第0号瓶：
01 - 1号瓶
10 - 2号瓶
11 - 3号瓶
00 - 0号(4号)瓶
如此二分优化下来，4瓶药水，我们只需2只小兔子奉献，就可在1天内找出有毒药水；
下面我们把瓶子数量：
扩展到100瓶；套用二进制思路，只需7只就可在1天内找出有毒药水；
再扩展到1000瓶，只需10只就可在1天内找出有毒药水；
聪明的你想到答案了吗？看完这道题，你是否对二分法有了更深入的了解呢？
提示：
99的二进制表达式为：1100011；
999的二进制表达式为：1111100111；
严格来说，原题中的1000瓶解题思路并非是二分法，称之为十分法更为贴切（100瓶则应称之为七分法），但本质都是套用了二分法的思路，将问题规模缩小到原来的十分之一；
网友评论