二分查找
- Ⅰ 前言
- Ⅱ 无处不在的二分思想
- Ⅲ 二分查找的速度
- Ⅳ 二分查找的递归与非递归实现
- 1. 非递归实现
- 2. 递归实现
- Ⅴ 二分查找应用场景的局限性
- 1. 数据结构
- 2. 排列方式
- 3. 数据规模
- Ⅵ 进阶——二分查找的变形
- 1. 查找第一个值等于给定值的元素
- 2. 查找最后一个值等于给定值的元素
- 3. 查找第一个大于等于给定值的元素
- 4. 查找最后一个小于等于给定值的元素
Ⅰ 前言
这篇文章我将详细分析一种针对有序数据集合的查找算法：二分查找（Binary Search） 算法，也叫 折半查找算法。二分查找的思想非常简单，但是看似越简单的东西往往越难掌握。
唐纳德·克努特（Donald E.Knuth）在《计算机程序设计艺术》的第三卷《排序和查找》中说道：“尽管第一个二分查找算法于 1946 年出现，然而第一个完全正确的二分查找算法实现直到 1962 年才出现。”
所以千万不要小看了二分查找，我将会带领大家由浅入深地去探究一下这个算法。
Ⅱ 无处不在的二分思想
二分查找是一种非常简单易懂的快速查找算法，生活中随处可见。最常见的例子就是猜数游戏，一个人在比如说 0 ~ 99 中随便想一个数，另一个人猜，每猜一次，这个人会告诉他是大了还是小了，直到猜中为止。一般来说猜数的人都会猜中间的数，比如第一次猜 49，如果大了，下一次就猜 23，如果小了，就猜75，这样重复下去。
100以内的数字，七次就可以猜出来了。如果是 0 ~ 999，也只需要 10 次。这就是二分查找的思想。
现在回到实际的开发场景中，假设有有 1000 条订单数据，已经按照订单金额从小到大排序，每个订单金额都不同，并且最小单位是元。我们现在想知道是否存在金额等于 19 元的订单，如果存在，就返回订单数据，如果不存在则返回 null。
最简单的办法当然是从第一个订单开始，一个一个遍历这 1000 个订单，直到找到金额等于 19 元的订单为止。但这样查找会比较慢，最坏情况下，可能要遍历完这 1000条记录才能找到。这时候就应该用二分查找了。
我们先假设只有 10 个订单，金额分别是：7，12，19，32，52，61，74，86，88，99。
还是利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围。
其中，low 和 high 表示待查区间的下标，mid 表示带查找区间的中间元素下标。
总结一下，二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
Ⅲ 二分查找的速度
二分查找是一种非常高效的查找算法，我们来分析一下它的时间复杂度。
假设数据大小是 n ，每次查找后数据都会缩小为原来的一半，也就是会除以 2.最坏情况下，直到查找区间被缩小为空，才停止。
可以看出来，这是一个等比数列。其中 n/2k = 1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及到两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k = 1，我们可以求得 k = log2n，所以时间复杂度就是 O(log2n)。
O(log2n) 这种对数时间复杂度，是极其高效的，有时候比时间复杂度是常量级 O(1) 的算法还要高效。为什么呢？这就是 log2n的恐怖之处了。
即使 n 非常大，对应的 log2n 也非常小。比如 n = 232，这个数很大了吧，大约是 42 亿。也就是说，我们在 42 亿个数据里用二分查找一个数据，最多需要比较 32 次。
我们知道，用 大 O 标记法表示时间复杂度的时候，会省略掉常数、系数和低阶，对于常量级时间复杂度的算法来说，O(1) 有可能表示的是一个非常大的常量值，比如 O(1000)、O(10000)。所以，常量级时间复杂度的算法有可能还没有 O(log2n) 的算法执行效率高。
反过来。对数对应的就是指数。像我们知道的棋格上放麦子的故事，还有金融学中的复利效应，都很好地体现了指数的可怕，所以指数时间复杂度的算法在大规模数据面前是无效的。
Ⅳ 二分查找的递归与非递归实现
实际上，简单的二分查找并不难写，我们先从最简单、最基本的写起，再往后看烧脑的。
最简单的情况就是有序数组中不存在重复元素，我们在其中用二分查找值等于给定的数据。
1. 非递归实现
public static int binarySearch(int[] arr, int length, int value) {
int low = 0;
int high = length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
这段代码很简单，但是有三个容易出错的地方。
-
循环退出条件
注意是low <= high，而不是low < high -
mid 的取值
实际上，mid = (low +high) / 2这种写法是有问题的，因为如果 low 和 high 比较大的话，二者相加就有可能会溢出。改进的方法是将其计算方式改为low + (high - low) / 2。更进一步，如果要将性能优化到极致的话，我们可以用位运算来替代除法，low + ((high - low) >> 1)。 -
low 和 high 的更新
注意是low = mid +1，high = mid - 1。如果直接写成low = mid或high = mid，就有可能会发生死循环。比如，当high = 3,low = 3时，如果arr[3]不等于value，就会导致一直循环不退出。
实际上，二分查找除了用循环来实现，还可以用递归来实现。
2. 递归实现
package com.tyz.recursion_b_search.core;
public class BinarySearch {
public BinarySearch() {
}
public static int binarySearch(int[] arr, int length, int value) {
return binarySearchInternally(arr, 0, length - 1, value);
}
private static int binarySearchInternally(int[] arr, int low, int high, int value) {
if (low > high) {
return -1;
}
int mid = low + ((high - low) >> 1);
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
return binarySearchInternally(arr, mid + 1, high, value);
} else {
return binarySearchInternally(arr, low, mid - 1, value);
}
}
}
Ⅴ 二分查找应用场景的局限性
1. 数据结构
二分查找依赖的是顺序表结构，简单说就是数组。
那二分查找能否依赖其他数据结构吗？比如链表。答案是不可以。主要原因是二分查找算法需要按照下标随机访问元素。在之前的数组和链表数据结构讲解中我写过，数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。所以，如果使用链表存储，二分查找的时间复杂度就会变得很高。
2. 排列方式
二分查找针对的是有序数据。 这一点二分查找要求比较苛刻，数据必须是有序的，如果数据无序，我们需要先排序。在排序的讲解中我们知道，排序的时间复杂度最低是 O(nlog2n)。所以，如果我们针对的是一组静态的数据，没有频繁地插入、删除，我们可以进行一次排序，多次二分查找，这样排序的成本就被均摊了，二分查找的边际成本就会降低。
但是，如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都很高。
因此，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中，针对动态变化的数据集合，二分查找将不再适用。
3. 数据规模
数据量太小不适合用二分查找。
如果要处理的数据量很小，顺序遍历就足够了，二分查找和顺序遍历速度都差不多，二分查找只有在数据量比较大的时候，优势才比较明显。
不过这里也有例外。如果数据之间的比较操作非常耗时，不管数据量大小，都最好使用二分查找。比如，数组中存储的都是长度超过 400 的字符串，那么比较起来就会很耗时。我们需要尽可能减少比较次数，这时候二分查找就比顺序遍历更有优势。
那数据量小不建议用二分查找，那数据量很大呢？其实也不建议。数据量太大是不适合二分查找的。
二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，内存空间是连续的。如果我们有 1GB 的数据，用数组来储存，那就需要 1GB 的连续内存空间。我们的二分查找就是建立在这种数据结构之上的，所以数据量太大，无法用数组存储，也就无法使用二分查找算法了。
Ⅵ 进阶——二分查找的变形
前面简单的部分过去了，现在我们开始难的部分。在前言我引述了一段唐纳德·克努特的话，足以说明二分查找的看似简单却非常容易写错的特性，不知道你有没有听过一句话，“十个二分九个错”，所以希望大家能好好对待二分查找，不要轻浮它。
闲话到此，我们开始正题。
其实二分查找的变形问题很多，但这里我选取四个最典型的来讲解，大道归一，其他的问题可以基于这四个问题的思想推出。特别说明一下，这几个变形我都是以数据从小到大排列为前提的，如果你要处理的数据是从大到小排列的，思路是一样的。
1. 查找第一个值等于给定值的元素
比如下面这样一个有序数组，其中，arr[5]，arr[6]，arr[7] 的值都等于 8，是重复的数据。我们希望查找到第一个等于 8 的数据，也就是下标为 5 的元素。
如果用简单的二分查找，那最后找到的下标就是 7 ，但是这并不是我们要找的第一个元素，所以前面简单的二分查找是无法处理这种情况的，我们需要做个变形，改造一下这个代码。
网上这个变形的代码很多了，有的思路非常简洁，但是并不好理解，我写在下面做个参考。
public static int binarySearch(int[] arr, int length, int value) {
int low = 0;
int high = length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] >= value) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (low < length && arr[low] == value) {
return low;
} else {
return -1;
}
}
这个思路其实是比较难想的，也很容易写错。下面我用一个我认为更好理解的方式来实现，大家可以选一个自己喜欢的来看。
public static int bsearch(int[] arr, int length, int value) {
int low = 0;
int high = length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
if (mid == 0 || arr[mid - 1] != value) {
return mid;
} else {
high = mid - 1;
}
}
}
return -1;
}
arr[mid]和要找的 value 的大小关系有三种情况：大于、小于、等于。对于 arr[mid] < value 的情况，我们需要更新 low = mid + 1；对于arr[mid] > value的情况，我们需要更新 high = mid - 1；这两点和最初是一样的，那arr[mid] == value的时候应该如何处理呢？
由于我们需要查找value 第一次出现的位置，所以找到和它相等的值时，我们需要先确认这是不是第一个。如果 mid == 0，那就说明这个元素已经是数组的第一个元素了，所以肯定也是我们要找的。如果 mid != 0，但是 arr[mid]的前一个元素 arr[mid-1]不等于value，那也说明 arr[mid] 就是我们要找的第一个值等于给定值的元素。
如果经过检查之后发现， arr[mid-1]也等于value，那说明arr[mid]肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新 high = mid - 1，因为要找的元素肯定出现在 [low, mid - 1] 之间。
很多人都觉得变形的二分查找很难写，主要原因是太追求第一种那样完美、简洁的写法。但是其实对于做工程开发的人来说，代码易读懂、没 Bug，更重要。
2. 查找最后一个值等于给定值的元素
这个其实和第一个变形是很像的，思路是一致的，我直接将代码给出。
public static int bsearch(int[] arr, int length, int value) {
int low = 0;
int high = length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
if ((mid == length - 1) || arr[mid + 1] != value) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
如果 arr[mid]这个元素已经是数组中的最后一个元素了，那它肯定是我们要找的；如果 arr[mid]的后面一个元素 arr[mid + 1]不等于 value，那也说明arr[mid]就是我们要找的最后一个值等于给定值的元素。
如果 arr[mid + 1]也等于 value，那说明当前的这个arr[mid]并不是最后一个值等于给定值的元素，我们就更新 low = mid + 1，因为要找的元素肯定在 [mid +1, high] 之间。
3. 查找第一个大于等于给定值的元素
现在我们再来看另一类变形问题。在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储着 {1, 2, 3, 6, 8}。如果查找第一个大于等于 4 的元素，那就是 6。
实际上，实现的思路和前面两种变形很类似，并且实现更简洁一点。
public static int bsearch(int[] arr, int length, int value) {
int low = 0;
int high = length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] >= value) {
if ((mid == 0) || arr[mid - 1] < value) {
return mid;
} else {
high = mid - 1;
}
} else {
low = mid + 1;
}
}
return -1;
}
如果 arr[mid]小于要查找的值 value，那要查找的值肯定在 [mid +1, high] 之间，所以，我们更新 low = mid + 1。
对于arr[mid] 大于等于给定值 value的情况，我们要先看下这个 arr[mid]是不是我们要找的第一个值大于等于给定值的元素。如果 arr[mid]前面已经没有元素，或者前面一个元素小于要查找的值 value，那arr[mid]就是我们要找的元素。
如果 arr[mid - 1]也大于等于要查找的值 value，那说明要查找的元素在 [low, mid - 1] 之间，所以要将 high 更新为 high = mid - 1。
4. 查找最后一个小于等于给定值的元素
现在来看最后一种变形问题，比如一个数组 {1, 3, 5, 7, 9, 11, 24}，要找最后一个小于等于 8 的元素，那就是 7，和第三种变形是很类似的，思路也是一样的。我不再做分析，直接将代码贴出来。
public static int bsearch(int[] arr, int length, int value) {
int low = 0;
int high = length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else {
if ((mid == 0) || (arr[mid + 1] > value)) {
return mid;
} else {
low = mid + 1;
}
}
}
return -1;
}
