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

前言

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

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

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

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

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

算法原理

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

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

标签：二分,target,索引,查找,目标值,图解,data,left
From： https://blog.51cto.com/u_14014612/6031703