二分查找及其变体

柔情只为你懂 2022-02-23 04:26 176阅读 0赞

## 二分查找及其变体 ##

*  说到二分查找，大家肯定不陌生。就举个生活中的例子吧，相信很多人肯定玩过猜数字的游戏：大概就是我随便说一个数字，告诉你范围（比如这个数字在1到100之间），然后看你猜多少次能猜出这个数字是多少。
 *  怎么猜才能在最短的次数之内找到正确答案呢？很简单，首先从50开始猜起，然后25或者75…以此类推，每次折半，直到找出正确答案。其背后的思想就是典型的二分查找，二分查找的效率之高，其时间复杂度为O(logaN)。哪怕是从上十亿级别的数据中查找一个数字，也只需要三五十次就能找到答案。假如：从50亿数字中找出一个数字，只需要n次即可->2的n次方=50亿，n = log50亿。

**但是，但是，但是！！！重要的话要说三遍：  
1.首先，二分查找对数据是有要求的，必须是有序数据集合，也就是有序数组；  
2.然后，数据量太小的话不适合二分查找，因为没必要，只需直接遍历就够了，杀鸡焉用牛刀；  
3.最后，数据量太大也不适合用二分查找，因为二分查找依赖数组这种数据结构，而数组要求连续的内存空间，注意连续二字！就算内存空间大于数据大小，但是如果是非连续的是行不通的。有了解过标记清除算法的朋友应该知道，这种GC算法是会产生大量的内存碎片的，导致内存空间不连续。**

说了这么多，那么二分查找用代码具体该如何实现呢？废话就不多说了，直接看代码：

/**
         * 二分查找第一版本
         * 这里的low、high、middle指的是数组的下标，n是数组的大小，value是要查找的数字。
         *
         * @param arr   有序数据集合
         * @param n     数据量的大小
         * @param value 要查找的数字
         * @return 要查找的数字
         */
        public static int erfen(int[] arr, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int middle = (low + high) / 2;  //取中间数进行比较
                if (arr[middle] == value) {
                    return value;               //等于中间数，则直接返回
                } else if (arr[middle] < value) {
                    low = middle + 1;           //大于中间数，则将查找范围缩小到后面一半
                } else {
                    high = middle - 1;          //小于中间数，则将查找范围缩小到前面一半
                }
            }
            return -1;
        }

这里需要注意的是：

*  middle这样写，如果low和high比较大的话，两者相加超出了int的取值范围，则会造成溢出问题。同时对于除以2的写法，可以优化成位运算(>>1)，因为计算机底层是二进制，相对除法，处理位运算速度更快。所以可以做如下优化：  
    `int middle = (low + high) / 2 -> int middle = low + ((high - low) >> 1)`

ok，上面是二分查找第一版，也是最简单的。数组是无重复数据并且已经排序好了的。如果数组中存在重复元素，我们要查找第一个值等于给定值的数据，该如何实现呢？

**第二版：查找第一个值等于给定值的数据**  
老规矩，我们直接看代码：

/**
         * 二分查找第二版本
         * 这里的low、high、middle指的是数组的下标，n是数组的大小，value是要查找的数字。
         *
         * @param arr   有序数据集合
         * @param n     数据量的大小
         * @param value 要查找的数字
         * @return      要查找的数字所在的数组下标
         */
        public static int erfen(int[] arr, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int middle = low + ((high - low) >> 1);
                if (arr[middle] > value) {
                    high = middle - 1;
                } else if (arr[middle] < value) {
                    low = middle + 1;
                } else {
                    if ((middle == 0) || arr[middle - 1] != value) {
                        return middle;
                    }
                    high = middle - 1;
                }
            }
            return -1;
        }

简单说明一下：

*  三种情况，大于、小于、等于，对于大于和小于都很好理解，直接更新查找范围即可；
 *  对于等于，则需要额外判断，如果middle=0，说明已经是数组的第一个元素了，直接返回即可。或者middle的前一个元素不等于value，也可以说明middle下标所在元素就是第一个出现。二者皆不符合，则继续缩小查找范围。

ok，继续第三版。  
**第三版：查找最后一个值等于给定值的数据**  
这个和查找第一个很类似，就不多说啥了，直接看代码吧：

/**
         * 二分查找第三版本
         * 这里的low、high、middle指的是数组的下标，n是数组的大小，value是要查找的数字。
         *
         * @param arr   有序数据集合
         * @param n     数据量的大小
         * @param value 要查找的数字
         * @return      要查找的数字所在的数组下标
         */
        public static int erfen(int[] arr, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int middle = low + ((high - low) >> 1);
                if (arr[middle] > value) {
                    high = middle - 1;
                } else if (arr[middle] < value) {
                    low = middle + 1;
                } else {
                    if ((middle == n - 1) || arr[middle + 1] != value) {
                        return middle;
                    }
                    low = middle + 1;
                }
            }
            return -1;
        }

**第四版：查找第一个值大于等于给定值的数据**  
这个和上面的大同小异，直接看代码：

/**
         * 二分查找第四版本
         * 这里的low、high、middle指的是数组的下标，n是数组的大小，value是要查找的数字。
         *
         * @param arr   有序数据集合
         * @param n     数据量的大小
         * @param value 要查找的数字
         * @return      要查找的数字所在的数组下标
         */
        public static int erfen(int[] arr, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int middle = low + ((high - low) >> 1);
                if (arr[middle] >= value) {
                    if ((middle == 0) || arr[middle - 1] < value) {
                        return middle;
                    }
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
            return -1;
        }

**第五版：查找最后一个值小于等于给定值的数据**

/**
         * 二分查找第五版本
         * 这里的low、high、middle指的是数组的下标，n是数组的大小，value是要查找的数字。
         *
         * @param arr   有序数据集合
         * @param n     数据量的大小
         * @param value 要查找的数字
         * @return      要查找的数字所在的数组下标
         */
        public static int erfen(int[] arr, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                int middle = low + ((high - low) >> 1);
                if (arr[middle] <= value) {
                    if ((middle == n - 1) || arr[middle + 1] > value) {
                        return middle;
                    }
                    low = middle + 1;
                } else {
                    high = middle - 1;
                }
            }
            return -1;
        }