摘要
二分法查找算法是一种在有序数组中查找特定元素的搜索算法。首先，梳理二分查找算法实现原理；其次，提供二分查找算法的三种不同实现；最后，分析该算法的局限性。
前言
在大学上算法分析课的时候，老师就说二分查找算法是一种效率较高的、适用于数据量较大序列的搜索算法，此算法基于顺序存储结构的线性表，且要求序列中元素按关键字有序排列，升序和降序都可以。
二分法的时间复杂度是O(logn)，所以在算法中，比O(n)更优的时间复杂度几乎只能是O(logn)的二分法。根据时间复杂度来倒推算法也是面试中的常用策略：题目中若要求算法的时间复杂度是O(logn)，那么这个算法基本上就是非二分法莫属。故本文浅析其三种实现方法，使大家对它有一个更深刻的认知。
在分析二分查找算法之前，我们先梳理计算机中有哪些数据结构。常见的数据结构有数组（Array）、堆栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、图（Graph）、堆（Heap）、散列表（Hash）。
算法原理
二分法又可以被称为二分查找(binary search)或者折半检索，其基本思想是对于一个有序数组，每次都通过与数组中间元素对比，将问题规模缩小为之前的一半，直到找到目标值。广义的二分查找是将问题的规模尽可能的缩小到原有的一半。这里用到了数组这种数据结构，它属于常见数据结构之一。
二分查找的原理如下：假设待搜索序列是按照升序排列的，则
-
如果序列为空，那么就返回-1，并退出算法；这表示查找不到目标值。
-
如果序列不为空，则将它的中间元素与目标值进行比较，看它们是否相等。
-
如果相等，则查找成功，返回该中间元素的索引并退出。
-
如果中间元素大于目标值，那么就将序列的前半部分作为新的待搜索序列；这是因为后半部分的所有元素都大于目标值，故可以被排除。
-
如果中间元素小于目标值，那么就将当前序列的后半部分作为新的待搜索序列；这是因为前半部分的所有元素都小于目标值，故可以被排除。
-
对新的待搜索序列重新执行第1步的工作。
二分查找之所以是一种效率较高的检索方法，是因为在匹配失败的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标值的有效区间就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。
基于折半检索寻找一个数
这是折半检索算法最简单的应用场景，可能也是大家最熟悉的，即在指定搜索范围内搜索一个数，如果存在，返回其索引；否则，返回 -1。下面给出两种非递归方式的折半检索实现方案：
import java.util.Arrays;
/**
* 二分法查找
*
* @author Wiener 使用二分法的前提是数组已经排序
*
*/
public class Demo {
public static void main(String[] args) {
int[] arr = { 3, 1, 8, 2, 9, 100,200, 33, 22, 11, 18, 14, 17, 15, 3 };
// 使用Arrays.sort()排序
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
// 返回结果
//int index = binarySearch(arr, 99);
int index = binarySearch_2(arr, 11);
System.out.println("index=" + index);
}
/**
* 二分法查找一返回下标
* @param arr 数组
* @param key 待匹配的值，看数组中是否存在
* @return key 在数组中的下标，如果是-1，就说明数组中不存在此元素
*/
public static int binarySearch(int[] arr, int key) {// 数组和要查找的数
int min = 0; // 最小的下标
int max = arr.length - 1;// 最大的下标
int mid = (min + max) / 2;// 中间的下标
while (arr[mid] != key) { // 用于于缩小查找范围
if (key > arr[mid]) { //比中间数还在
min = mid + 1; //使最小的下标=中间下标+1
} else if (key < arr[mid]) {//比中间数还小
max = mid - 1; //使最大的下标=中间下标-1
}
if(max<min){
return -1;
}
mid=(min+max)/2; //再次计算中间下标
}
return mid;
}
/*
* 二分法查找一如果返回的下标是-1，就说明没有
*/
public static int binarySearch_2(int[] arr, int key) {// 数组和要查找的数
int min = 0; // 最小的下标
int max = arr.length - 1;// 最大的下标
int mid = min + (max - min) >> 1;// 中间数下标，等价于(min + max) / 2
while(min<=max){
if(key>arr[mid]){
min=mid+1;
}else if(key<arr[mid]){
max=mid-1;
}else{
return mid;
}
mid=(min+max)/2;
}
//没找到
return -1;
}
}
分析二分查找算法的一个技巧是：尽量避免出现 else，而是把所有情况用 else if 写清楚，这样可以清晰地展现所有细节。
温馨提示，退出循环的条件之所以是min<=max，而不是min<max，是因为 max = arr.length - 1。
关于mid如何取值，实际上，mid=(min + max) / 2 这种写法是有缺陷的。因为如果min和max比较大的话，两者之和就有可能会溢出。改进的地方是将mid的计算方式写成min + (max - min) >> 1。因为相比除法运算来说，计算机处理位运算性能提升很多。
二分法的递归实现
实际上二分查找除了以循环遍历来实现，还可以用递归来实现。代码如下：
/**
* 递归思想实现二分查找
*
* @param orderedArray 有序数组
* @param low 数组最小值下标
* @param high 数组最大值下标
* @param key 查找元素
* @return 查找元素不存在返回-1，存在返回对应的数组下标
*/
public static int internallyBinarySearch(int orderedArray[], int low, int high, int key) {
int mid = (high - low) / 2 + low;
if (orderedArray[mid] == key) {
return mid;
}
if (low >= high) {
return -1;
} else if (key > orderedArray[mid]) {
return internallyBinarySearch(orderedArray, mid + 1, high, key);
} else {
return internallyBinarySearch(orderedArray, low, mid - 1, key);
}
}
应用场景的局限性
二分查找的时间复杂度是 O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大局限性的。那什么情况下适合用二分查找，什么情况下不适合呢？
首先，二分查找依赖的是顺序表结构，简单点说就是数组。二分查找只能用在数据是通过顺序表来存储的数据结构上。如果你的数据是通过
链表等其它数据结构存储的，则无法实现二分查找。
其次，二分查找针对的是有序序列。二分查找对这一点的要求比较苛刻，数据必须是有序的。如果数据没有排序，我们需要先排序，排序的时间复杂度最低是 O(nlogn)。所以，我们如果针对的是一组静态数据，而且没有频繁地插入、删除，那么可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。
但是，如果我们的数序列有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都是很高的。
所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。
再次，数据量太小不适合二分查找。数据量很小时，顺序遍历就足够了，完全没有必要用二分查找。只有数据量比较大的时候，二分查找的优势才会比较明显。
有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找。比如，数组中存储的都是长度超过 300 的字符串，如此长的两个字符串之间比对大小，就会非常耗时。我们需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势。
最后，数据量太大也不适合二分查找。二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如，我们有 1GB 大小的数据，如果希望用数组来存储，那就需要 1GB 的连续内存空间，但是我们的内存都是离散的，可能电脑没有这么多的内存。
注意这里的“连续”二字，也就是说，即便有 2GB 的内存空间剩余，但是如果这剩余的 2GB 内存空间都是零散的，没有连续的 1GB 大小的内存空间，那照样无法申请一个 1GB 大小的内存空间，那照样无法申请一个 1GB 大小的数组。而我们的二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较吃力了，也就不能用二分查找了。
如何在 1000 万个整数中快速查找某个整数？
假设内存限制是 100MB，每个数据大小是 8 字节，最简单的办法就是将数据存储在数组中，内存占用差不多是 10000000/1024/1024 ≈ 76.3MB，符合内存的限制。我们可以先对这 1000 万数据进行排序，然后再利用二分查找算法，就可以快速地查找想要的数据了。
欢迎点赞阅读，一同学习交流；若有疑问，请在文章下方留下你的神评妙论！
Reference
https://zhuanlan.zhihu.com/p/65610304
https://blog.csdn.net/weixin_41923658/article/details/86090645
https://www.cnblogs.com/gshao/p/13489436.html#_label3
赞赏支持