二分查找法是一个经典查找算法，也是面试中经常出现的一种算法，它以时间复杂度低而著称并广受喜爱。本文整理一些二分的知识并分享一些算法和体验。
时间复杂度
二分查找是一种非常高效的查找算法。
假设数据个数是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。
被查找区间的大小变化：
n, n/2, 2/4, n/8, … n/2^k
这是一个等比数列，其中 n/2^k=1 时， k 的值就是总共缩小的次数，每次缩小操作只涉及两个数据的大小比较，所以，经过 k 次区间缩小操作，时间复杂度为 O(k)。
通过 n/2^k=1， 可以求得 k = log2^n ，所以时间复杂度就是 O(logn)。
O(logn) 对数时间复杂度
这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。
为什么这么说呢？
因为 logn 是一个非常“恐怖”的数量级，即便 n 非常非常大，对应的 logn 也很小。比如 n 等于 2 的 32 次方，n 大约是 42 亿。也就是说，如果我们在 42 亿个数据中用二分查找一个数据，最多需要比较 32 次。
在用大 O 标记法表示时间复杂度的时候，会省略掉常数、系数和低阶。
对于常量级时间复杂度的算法来说，O(1) 有可能表示的是一个非常大的常量值，比如 O(1000)、O(10000)。所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。
反过来，对数相对的就是指数。这也是为什么，指数时间复杂度的算法在大规模数据面前是无效的。
简单二分查找的递归与非递归实现
简单二分查找，是指在不存在重复元素的有序数据中查找值等于给定值的数据。
递归方式
递归是最容易想到的写法，它的好处就是代码清晰明了。思路：
- 首先找到「出口」，即退出方法的条件：1）如果mid正好是要找的target，那么直接返回即可；2）否则如果start>=end，则已经没有可能找到
- 找到参数变化的可能性，并区分不同可能性对参数以及递归的影响：1）如果a[mid]小于target，从mid+1为左边界继续找，end不变；2）如果a[mid]比target大，从mid-1 为右边界继续找，start不变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int srcArray[], int start, int end, int target) {
if (start >= end) {
return -1;
}
int mid = (end - start) / 2 + start;
if (target == srcArray[mid]) {
return mid;
} else if (target > srcArray[mid]) {
return binarySearch(srcArray, mid + 1, end, target);
} else {
return binarySearch(srcArray, start, mid - 1, target);
}
}
非递归方式
有了递归方式，将其转化为非递归就容易一些了，将递归的部分参数挪到循环外部定义，并以「全局」变量的形式参与计算。思路：
- 将递归拆解为
while循环，找到「跳出条件」：start>end，此时已经找完所有可能，下标已经不再符合正常逻辑，直接退出 while内部的计算：每一轮只需要计算对应的变量的值并进行相同的比较逻辑即可，找到符合条件的直接退出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int binarySearch(int srcArray[], int target) {
int mid;
int start = 0;
int end = srcArray.length - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
if (target < srcArray[mid]) {
end = mid - 1;
} else if (target > srcArray[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
注意返回值为
-1时的写法，while中的条件是start<=end。注意问题
- 关于mid的计算，并没有使用简单的
(start+end)/2的方式，因为在两个值都是非常大的数字的时候加和是可能存在溢出风险的- start和end的更新问题，不能使用start=mid或end=mid，可能会导致死循环 比如，当 high=3，low=3 时，如果 arr[3] 不等于 ele，就会导致一直循环不退出。
这里只是最简单的二分查找，实际生产中，我们可能面对的是：
找出第一个值等于key的元素，或者找出最后一个值等于key的元素，甚至还有找出第一个<= 或者>=的元素位。
应用场景的局限性
此部分参考自ipine的blog，感谢她的精彩总结。 二分查找的时间复杂度是
O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景有很大局限性。
1 . 二分查找依赖的是顺序表结构，即数组。 二分查找不能依赖于其他数据结构，比如链表。主要原因是二分查找算法需要按照下标随机访问元素。数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。
2 . 二分查找针对的是有序数据。如果数据没有序，需要先排序。排序的时间复杂度最低是 O(nlogn)。所以，如果针对的是一组静态的数据，没有频繁地插入、删除，就可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。
针对有频繁插入、删除操作的这种动态数据集合，二分查找是不适用的。要用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都很高。
3 . 数据量太小不适合二分查找。如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。只有数据量比较大的时候，二分查找的优势才会比较明显。
有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找。比如，数组中存储的都是长度超过几百的字符串，如此长的两个字符串之间比大小，就会非常耗时。为了尽可能地减少比较次数，二分查找就比顺序遍历更有优势。
4 . 数据量太大也不适合二分查找。二分查找依赖的是数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较困难，就不能用二分查找了。
Q. 若二分查找依赖于链表结构，时间复杂度如何分析？
假设链表长度为 n，二分查找每次需要找到中间点，那么总共需要移动的指针次数为：
n/2 + n/4 + n/8 + … + 1
这也是一个等比数列，根据等比数列求和公式 (S = (a1-an*q)/1-q, q为公比, 且不为1)，其和等于 n-1 。所有最后算法时间复杂度为 O(n)。
时间复杂度和顺序查找时间复杂度相同，但是，在二分查找的时候，由于要进行多余的运算，严格来说，会比顺序查找时间慢。
变种：求范围
另外有一个问题就是上面的代码其实在遇到第一个符合条件的数字之后就退出了，如果我们的数组里面有大量重复的数字，并且想知道这个数字的下标范围该怎么做呢？ 其实，这个也是二分思路，但是逻辑需要做一定的调整。
这道题分享自hk029。
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found
in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
题目中说要求时间复杂度为 O(logn) ，作为查找算法，还是有序数组，默认都应该考虑到使用二分查找。
这里需要返回两个值：左边界和右边界，如果用传统的思路，会很容易找到一个符合条件的位置，但是这个位置的左侧和右侧到底还有没有相同的值呢？
难道需要向左或向右一位一位继续判断吗？显然那样的时间复杂度是 O(N) ，所以需要使用二分的方式分别对左边界和右边界进行计算。
左边界计算
先计算左边界，确定了最左侧的边界后再往右侧计算就容易很多了，而如何确定最左边界而不会导致左侧还有符合条件的数？ 需要对传统的二分计算规则做一定的调整：
- Rule 1. A[mid] < target ，这时候说明还可以向右，st = mid+1
- Rule 2. A[mid] > target ， 这时候说明应该在左边，ed = mid-1
- Rule 3. A[mid] == target ，这时候既可以左移，也可以不移动，ed = mid
考虑下面几种情况，假设 target=5：（在两个数的情况下mid = st）
case 1: [3 5] (A[st] < target = A[ed])
case 2: [5 7] (A[st] = target < A[ed])
case 3: [5 5] (A[st] = target = A[ed])
case 4: [3 7] (A[st] < target < A[ed])
case 5: [3 4] (A[st] < A[ed] < target)
case 6: [6 7] (target < A[st] < A[ed])
case1就是Rule1的情况，st = mid + 1就行。 对于case2-3这时候，我们只要 ed = mid就行了，其实也就是把Rule 2 和Rule 3合并成了：
Rule 2*. A[mid] >= target， ed = mid
所以case 1-3 最后停止条件都是A[st] = A[ed] = target 对于case 4-6 都是A[st] != target，可以直接退出
右边界计算
已经找到了左边界，右边界的计算已经有了新start，则计算start和end之间的部分即可。还有一点要注意，此时范围内的数值都是>=target的。
这里，我们让mid偏向右边mid = (st + ed)/2 + 1;然后主要控制ed移动就可以了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
public int[] searchRange(int[] nums, int target) {
int [] result = new int [2];
result[0] = result[1] = -1;
if(nums.length == 0)
return result;
int start = 0, end = nums.length-1, mid;
// 寻找左边界
while(start < end) { // 这里没有=的条件，在跳出后做逻辑
mid = (end - start) / 2 + start;
if (nums[mid] < target) //保证start不会越过任何等于target的数
{
start = mid + 1; // 缩小左侧范围，排除不符合条件的数
} else {
// 如果大于，将end移动到mid，缩小右侧范围，排除不符合条件的数
// 如果等于，此时不能跳出，因为左侧仍然可能包括符合条件的数，所以必须移动end，此处移动到mid
end = mid; // 不会发生死循环，因为条件是start<end
}
}
// 此时start==end，如果不为target则退出
if(nums[start] != target)
return result;
result[0] = start;
// 寻找右边界
end = nums.length-1; // 调整ed为最大位置
while(start < end)
{
mid = (end - start) / 2 + start + 1; //这里用+1是为了让mid偏向右边
if(nums[mid] > target)
{
end = mid-1; // 缩小右侧范围，排除不符合条件的数
}
else{ //因为start已经确定了，所以这里实际上不会出现比target小的数了，这里实际就是A[mid] == target
start = mid; // 将start往右移动，start和result[0]之间的数都是符合条件的数，继续压缩和end之间的空间在计算
}
}
// 此时start==end，因为start初始值是合法的，这里直接赋值end给result即可
result[1] = end;
return result;
}
}
References
- https://ipine.me/2018-11-08/
- https://hk029.gitbooks.io/leetbook/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/034.%20Search%20for%20a%20Range[M].html
本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.
