简介

二分查找，又叫折半查找，是一种查询效率非常高的查找算法，其实我更喜欢叫“折半查找”，一听这名字就知道每次在所有内容的前一半或者后一半进行查找。好了，下面咱们言归正传，通过简单讲解和两种方式实现的例子说明这么效率高的算法，还是老规矩，一个字：干

规则

必须是有序的序列，这个规则很容易理解，要不全部是降序，要不全部是升序，不能是无规则的内容，因为要通过查询内容中的元素进行大小的判断，决定从后半部分还是前半部分进行继续查找。

优缺点

优点	缺点
比较次数少查找速度快，平均性能好	待查表为有序表，且插入删除困难

因此，折半查找方法适用于不经常变动而查找频繁的有序列表

图示说明

image.png

递归实现

 /**
     * 执行入口
     *
     * @param args
     */
    public static void main(String args[]) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 18, 21, 22, 25, 28, 29, 32, 41, 46, 47, 48, 49, 50, 51, 52, 53};
        System.out.println(recursionSearch(arr, 22, 0, arr.length - 1));
    }

/**
     * 递归方式进行二分查找（折半查找）
     *
     * @param arr  数组
     * @param key  查找内容
     * @param star 查找开始下标
     * @param end  查找结束下标
     * @return
     */
    public static int recursionSearch(int[] arr, int key, int star, int end) {
        // 锁定边界 前进条件
        if (star <= end) {
            // 取中间数
            int middle = (star + end) / 2;
            // 如果查找内容小于中间数，则折半后，从前一半中再次折半查找
            if (arr[middle] > key) {
                return recursionSearch(arr, key, star, middle - 1);
                //如果查找内容大于中间数，则折半后，从后一半中再次折半查找
            } else if (arr[middle] < key) {
                return recursionSearch(arr, key, middle + 1, end);
            } else {
                // 找到对应的数后跳出
                return middle;
            }
        }
        return -1;
    }

循环方式

 /**
     * 执行入口
     *
     * @param args
     */
    public static void main(String args[]) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 18, 21, 22, 25, 28, 29, 32, 41, 46, 47, 48, 49, 50, 51, 52, 53};
        System.out.println(circularSearch(arr, 22));
    }

    /**
     * while 循环方式进行二分查找（折半查找）
     *
     * @param arr 数组
     * @param key 查找内容
     * @return
     */
    public static int circularSearch(int[] arr, int key) {
        // 开始下标
        int star = 0;
        // 结束下标
        int end = arr.length - 1;
        while (star <= end) {
            //取中间数
            int middle = (star + end) / 2;
            // 如果查找内容等于数据中某一数，跳出循环返回
            if (arr[middle] == key) {
                return middle;
                // 如果查找内容小于该数，则截至下标为中间数-1
            } else if (arr[middle] > key) {
                end = middle - 1;
                // 如果查找内容大于该数，则开始下标为中间数+1
            } else if (arr[middle] < key) {
                star = middle + 1;
            }
        }
        return -1;
    }

下面来自网络摘抄，目前还没太研究时间复杂度和空间复杂度。

时间复杂度（）

采用方式：分治策略
最坏的情况下两种方式时间复杂度一样：O(log2 N)

image

最好情况下为O（1）

空间复杂度

空间复杂度并不指计算实际占用的空间，而是计算整个算法的辅助空间单元的个数。

非递归方式：
由于辅助空间是常数级别的所以：
空间复杂度是O(1);

递归方式：
递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：
空间复杂度：O(log2N )

结束语

如果有什么问题可以留言，大家共同学习。