二分查找算法实现（图解）与实例

前言

当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找又叫折半查找。

 

它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以，本文假设是升序排列的），二是该序列必须是顺序存储的。

 

如果一个序列是无序的或者是链表，那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件，是由二分查找算法的原理决定的。

 

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

 

二分查找能应用于任何类型的数据，只要能将这些数据按照某种规则进行排序。然而，正因为它依赖于一个有序的集合，这使得它在处理那些频繁插入和删除操作的数据集时不太高效。这是因为，对于插入和操作来说，为了保证查找过程正常进行，必须保证数据集始终有序。相对于查找来说，维护一个有序数据集的代价更高。此外，元素必须存储在连续的空间中。因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找是最好的选择。

算法原理

二分查找算法的原理如下：

• 1、如果待查序列为空，那么就返回-1，并退出算法；这表示查找不到目标元素。

• 2、如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等。

• 3、如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了。

• 4、如果不相等，就再比较这两个元素的大小。

• 5、如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了。

• 6、如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了。

• 7、在新的待查序列上重新开始第1步的工作。

二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。

二分查找的实现与分析

二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。

 

此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。

• 首先，将left和right分别设置为0和size-1。在循环的每次迭代过程中，将middle设置为left和right之间区域的中间值。
• 如果处于middle的元素比目标值小，将左索引值移动到middle后的一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。
• 如果处于middle的元素比目标元素大，将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据集的下半区。
• 随着搜索的不断进行，left从左向右移，right从右向左移。一旦在middle处找到目标，查找将停止；如果没有找到目标，left和right将重合。下图显示了此过程。

二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说，最多可以进行O(㏒₂n)次分区。对于二分查找，这表示最终可能在最坏的情况下执行的检查的次数：例如，在没有找到目标时。所以二分查找的时间复杂度为O(㏒₂n)。

二分查找的实现

2.1、非递归实现方式

/** * @Author: huangyibo * @Date: 2022/1/23 16:42 * @Description: 二分查找法 非递归实现方式 * 文字描述: * 1、前提：数组需有序 * 2、定义左边界L, 右边界R, 确定搜索范围, 执行二分查找 * 3、获取中间索引 M = (L + R) / 2 * 4、中间索引的值 A[M] 与待搜索的值 T 进行比较 * 1、A[M] == T 表示找到, 返回中间索引 * 2、A[M] > T 中间值右侧的其他元素都大于 T, 无需比较, 中间索引左边去找, M - 1 设置为右边界, 重新查找 * 3、A[M] < T 中间值左侧的其他元素都小于 T, 无需比较, 中间索引右边去找, M + 1 设置为左边界, 重新查找 * 5、当 L > R 时, 表示没有找到, 应结束循环 * * 注意: * 1、目前二分查找是以JDK中的 Arrays.binarySearch()为实现 * 2、实际上二分查找有诸多变体，一旦使用变体的实现代码，则左右边界的选取会有变化 */ public class BinarySearch { /** * 二分查找，找到返回元素索引，没找到返回-1 * @param data 目标数组 * @param target 目标值 * @param <E> 泛型 * @return 返回目标值索引 */ public static <E extends Comparable<E>> int binarySearch(E[] data,E target){ int left = 0; int right = data.length - 1; while (left <= right){ //left、right 值特别大，会有溢出风险 //int mid = (left + right) / 2; //这种写法不会溢出 //int mid = left + (right - left) / 2; //使用位运算，正整数无符号右移一位和除2效果一样，效率更高 int mid = (left + right) >>> 1; if(data[mid].compareTo(target) == 0){ return mid; }else if(data[mid].compareTo(target) > 0){ right = mid - 1; }else { left = mid + 1; } } return -1; } }

2.2、递归实现方式

/** * @Author: huangyibo * @Date: 2022/1/23 16:42 * @Description: 二分查找法 递归实现方式 */ public class BinarySearch { /** * 递归方式二分查找法 找到返回元素索引，没找到返回-1 * @param data 目标数组 * @param target 目标值 * @param <E> 泛型 * @return 返回目标值索引 */ public static <E extends Comparable<E>> int binarySearch(E[] data,E target){ return search(data,0,data.length - 1,target); } /** * 递归方式二分查找法 找到返回元素索引，没找到返回-1 * @param data 目标数组 * @param left 左边界索引 * @param right 右边界索引 * @param target 目标值 * @param <E> 泛型 * @return 返回目标值索引 */ private static <E extends Comparable<E>> int search(E[] data, int left, int right, E target){ if(left > right){ return -1; } int mid = (left + right) >>> 1; if(data[mid].compareTo(target) > 0){ return search(data,left,mid - 1,target); }else if(data[mid].compareTo(target) < 0) { return search(data,mid + 1,right,target); } //mid索引元素和目标值相等 return mid; } }

2.3、二分查找法变种

• 查找比目标值大的最小值

/** * @Author: huangyibo * @Date: 2022/1/23 22:25 * @Description: 二分查找法变种 查找比目标值大的最小值 */ public class BinarySearch { /** * 查找比目标值大的最小值的索引 * @param data 目标数组 * @param target 目标值 * @param <E> 泛型 * @return 返回比目标值大的最小值的索引 */ public static <E extends Comparable<E>> int upper(E[] data,E target){ int left = 0; int right = data.length; //在data[left, right]中寻找解 while (left < right){ int mid = (left + right) >>> 1; if(data[mid].compareTo(target) <= 0){ //mid索引元素小于等于目标值，比目标值大的最小值在其右边区间 left = mid + 1; }else { //mid索引元素大于目标值， //比目标值大的最小值在其左边区间，有可能就是mid索引的值 right = mid; } } return left; } }

2.4、二分查找法变种

• 前提：有序数组中可能存在重复元素
• 1、目标值在有序数组中存在多个，返回最大索引
• 2、目标值在有序数组中不存在，返回比目标值大的索引

/** * @Author: huangyibo * @Date: 2022/1/23 22:38 * @Description: 二分查找法变种 * 前提：有序数组中可能存在重复元素 * 1、目标值在有序数组中存在多个，返回最大索引 * 2、目标值在有序数组中不存在，返回比目标值大的索引 */ public class BinarySearch { /** * 1、目标值在有序数组中存在多个，返回最大索引 * 2、目标值在有序数组中不存在，返回比目标值大的索引 * @param data * @param target * @param <E> * @return */ public static <E extends Comparable<E>> int ceil(E[] data,E target){ //获取到比目标值大的最小值的索引 int upper = upper(data, target); //如果upper索引的前一位元素等于目标值 //表示数组中元素存在目标值 if(upper - 1 >= 0 && data[upper - 1].compareTo(target) == 0){ return upper - 1; } //数组中元素不存在目标值 return upper; } /** * 查找比目标值大的最小值的索引 * @param data 目标数组 * @param target 目标值 * @param <E> 泛型 * @return 返回比目标值大的最小值的索引 */ private static <E extends Comparable<E>> int upper(E[] data,E target){ int left = 0; int right = data.length; //在data[left, right]中寻找解 while (left < right){ int mid = (left + right) >>> 1; if(data[mid].compareTo(target) <= 0){ //mid索引元素小于等于目标值，比目标值大的最小值在其右边区间 left = mid + 1; }else { //mid索引元素大于目标值， //比目标值大的最小值在其左边区间，有可能就是mid索引的值 right = mid; } } return left; } }

2.5、二分查找法变种

• 前提：有序数组中存在重复元素
• 1、目标值在有序数组中存在多个，返回最小索引
• 2、目标值在有序数组中不存在，返回比目标值大的索引

/** * @Author: huangyibo * @Date: 2022/1/23 22:38 * @Description: 二分查找法变种 * 前提：有序数组中存在重复元素 * 1、目标值在有序数组中存在多个，返回最小索引 * 2、目标值在有序数组中不存在，返回比目标值大的索引 */ public class BinarySearch { /** * 1、目标值在有序数组中存在多个，返回最小索引 * 2、目标值在有序数组中不存在，返回比目标值大的索引 * @param data * @param target * @param <E> * @return */ public static <E extends Comparable<E>> int lowerCeil(E[] data,E target){ //获取到比目标值大的最小值的索引 int upper = upper(data, target); //声明临时变量，temp int temp = upper - 1; //循环的前提是temp >= 0 while (temp >= 0){ //如果temp索引的元素等于目标值，说明目标在在数组中存在 if(data[temp].compareTo(target) == 0){ temp -- ; }else if(data[temp].compareTo(target) < 0){ //如果temp索引的元素小于目标值，则跳出循环 break; } } //数组中元素不存在目标值 return temp + 1; } /** * 查找比目标值大的最小值的索引 * @param data 目标数组 * @param target 目标值 * @param <E> 泛型 * @return 返回比目标值大的最小值的索引 */ private static <E extends Comparable<E>> int upper(E[] data,E target){ int left = 0; int right = data.length; //在data[left, right]中寻找解 while (left < right){ int mid = (left + right) >>> 1; if(data[mid].compareTo(target) <= 0){ //mid索引元素小于等于目标值，比目标值大的最小值在其右边区间 left = mid + 1; }else { //mid索引元素大于目标值， //比目标值大的最小值在其左边区间，有可能就是mid索引的值 right = mid; } } return left; } }

2.6、二分查找法变种

• 查找小于目标值的最大值

/** * @Author: huangyibo * @Date: 2022/1/23 23:07 * @Description: 二分查找法变种 查找小于目标值的最大值 */ public class BinarySearch { /** * 查找小于目标值的最大值 * @param data 目标数组 * @param target 目标值 * @param <E> 泛型 * @return 返回比目标值小的最大值的索引 */ public static <E extends Comparable<E>> int lower(E[] data,E target){ int left = -1; int right = data.length - 1; //在data[left, right]中寻找解 while (left < right){ //如果目标数组为{1, 1, 8, 11, 11, 11, 22,}, 目标值target为2或22，那么会陷入死循环 //这里采用这种方式获取mid的值的原因在于 //比目标值小的最大值存在多个的话，mid = (left + right) >>> 1 //mid的值取得是左边界的值，那么会陷入死循环中 //mid = (left + right + 1) >>> 1 mid的值取的是右边界的值，会规避死循环的问题 //int mid = left + (right - left + 1) / 2; int mid = (left + right + 1) >>> 1; if(data[mid].compareTo(target) < 0){ //mid索引元素小于等于目标值， //比目标值小的最大值在其右边区间，有可能就是mid索引的值 left = mid; }else{ //mid索引元素大于等于目标值，比目标值小的最大值在其左边区间 right = mid - 1; } } return left; } }

参考： https://www.html.cn/qa/other/23018.html

https://www.cnblogs.com/idreamo/p/9000762.html