前言

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

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

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

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

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

算法原理

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

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)。

二分查找的实现

/**
 * @author: huangyibo
 * @Date: 2021/11/17 15:10
 * @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 {

    public static void main(String[] args) {
        int[] arr = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};

        int search = binarySearch(arr, 48);
        System.out.println(search);
    }

    /**
     * 二分查找，找到返回元素索引，没找到返回-1
     * @param arr 目标数组
     * @param temp 目标值
     * @return 返回索引
     */
    public static int binarySearch(int[] arr, int temp) {
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left <= right){
            //left、right 值特别大，会有溢出风险
            //mid = (left + right) / 2;

            //这种写法不会溢出
            //mid = left + (right - left) / 2;

            //使用位运算，正整数无符号右移一位和除2效果一样，效率更高
            mid = (left + right) >>> 1;
            if(arr[mid] == temp){
                return mid;
            }else if(arr[mid] > temp){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

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

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