• 【算法】查找类——二分查找算法

    二分查找算法算法总结

    算法描述

    该算法属于查找算法。当需要从有序数组中查找某一元素时，可以使用该算法进行查找。（本文章假设数组是升序排列的数组）

    算法思想

    每次进行对半查找，获取中间元素值，然后与目标值进行比较。

    • 如果目标元素等于中间值，则查找成功，返回中间元素的index。
    • 如果目标元素小于中间值，则目标在中间值的左侧，则对中间值的左侧进行对半查找。
    • 如果目标元素大于中间值，则目标在中间值的右侧，则对中间值的右侧进行对半查找。

    当查找区间没有元素时，返回-1，表示没有找到。

    接口定义

    /**
 * 标准二分查找法, 在一个数据找找寻value。
 *
 * @param array 数组 升序排序
 * @param value 要找的数
 * @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1
 */
public int binarySearch(int[] array, int value) {}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    代码实现

    闭合区间实现方案

    /**
 * 标准二分查找法, 在一个数据找找寻value。
 *
 * @param array 数组 升序排序
 * @param value 要找的数
 * @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1
 */
public static int binarySearch(int[] array, int value) {
    int start = 0, end = array.length - 1;  // [start, end] 区间，start和end都能取得
    while (start <= end) {
        int mid = (start + end) >>> 1;
        if (array[mid] < value) {
            start = mid + 1;
        } else if (value < array[mid]) {
            end = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    半闭合区间实现

    /**
 * 标准二分查找法, 在一个数据找找寻value。
 *
 * @param array 数组 升序排序
 * @param value 要找的数
 * @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1
 */
public static int binarySearchEndOpen(int[] array, int value) {
    int start = 0, end = array.length;  // [start, end) 比区间，end不能去到, end指向非查找目标
    while (start < end) {
        int mid = (start + end) >>> 1;
        if (array[mid] < value) {
            start = mid + 1;
        } else if (value < array[mid]) {
            end = mid;
        } else {
            return mid;
        }
    }
    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    两个方案总结

    如果数据不存在相同元素时，该数组返回值时是相同的。

    如果数组存在相同元素时，查找相同元素时，返回的结果会存在不一致的现象。

    例子：在同一数组中查找89，一个结果为6，一个结果为7

            /**
         *  相同数查找
         *  1, 32, 32, 56, 78, 89, 89, 89, 122
         *  0	1	2	3	4	5	6	7	8
         */
        int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};
        Assert.assertEquals(6, BinarySearch.binarySearch(arrayExistSameValue, 89));
        Assert.assertEquals(7, BinarySearch.binarySearchEndOpen(arrayExistSameValue, 89));

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    二分查找算法拓展一 lower_bound 和upper_bound

    • 查找第一个大于等于value的值的位置。（C++ STL的 lower_bound实现了该算法。 Java leftMost）
    • 查找第一个大于value的值位置。（C++ STL的upper_bound实现了该算法。Java Left）

    算法模块

        /**
     * 二分查找模板
     * 
     * @param array
     * @param value
     * @return
     */
    public static int binarySearchTemplate(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) { // 
                end = mid - 1;
            } else if (midValue < value){
                start = mid + 1;
            } else {
                // todo 带补充的语句, 以下三选一
                // return mid;
                // end = mid - 1;
                // start = mid + 1;
            }
        }
        return start;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    • return mid; // 和默认的二分查找法相同，返回首次对半找到的值的index

    • end = mid - 1; // 返回第一个大于等于value的值的位置。

      ​ 存在等于value的元素时，查找区间一致往左移动。

    • start = mid + 1 // 返回第一个大于value的值位置

      ​ 存在等于value的元素时，查找区间一致往右移动。

    二分查找算法拓展二

        /**
     *  相同数查找
     *  0	1	2	3	4	5	6	7	8
     *  1, 32, 32, 56, 78, 89, 89, 89, 122
     */

    • 1
    • 2
    • 3
    • 4
    • 5

    lower_bound 返回第一个大于等于value的值的index 。 例子：返回的值为5

    upper_bound 返回第一个大于value的值的index。 例子：返回的值为8

    拓展二:

    lower_bound - 1 返回最后一个小于value的值的index。 例子：返回的值为4

    upper_bound - 1 返回最后一个小于等于value的值的index。例子：返回的值为7

    二分查找法的应用

    • x < 89 的范围 0… lower_bound - 1

    • x <= 89 的范围 0…upper_bound - 1

    • x > 89 upper_bound… 无穷

    • x >= 89 lower_bound … 无穷

    • == 89的数量 upper_bound - lower_bound

    将x替换为n时

    • x< n 的范围 0… lower_bound - 1

    • x<= n 的范围 0…upper_bound - 1

    • x > n upper_bound… 无穷

    • x=> n lower_bound … 无穷

    • x== n 的数量 upper_bound - lower_bound

    Java二分查找源码解析

    返回值说明：

    • 如果存在包含value，直接返回value的index
    • 如果不存在，返回-(insertion point) - 1。 insertion point是指可以插入的元素。 减一的原因：区分位置0.
        public static int binarySearch(int[] a, int fromIndex, int toIndex,
                                   int key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return binarySearch0(a, fromIndex, toIndex, key);
    }

    // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found. // low 表示第一个大于key的元素
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    代码实现

    默认实现

        /**
     * 标准二分查找法, 在一个数据找找寻value。
     *
     * @param array 数组 升序排序
     * @param value 要找的数
     * @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1
     */
    public static int binarySearch(int[] array, int value) {
        int start = 0, end = array.length - 1;  // [start, end] 区间，start和end都能取得
        while (start <= end) {
            int mid = (start + end) >>> 1;
            if (array[mid] < value) {
                start = mid + 1;
            } else if (value < array[mid]) {
                end = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    单元测试

        @Test
    public void testBinarySearch() {
        // 数据长度为单数 9
        int[] arraSingle = {1, 32, 34, 56, 78, 79, 89, 99, 122};
        Assert.assertEquals(0, BinarySearch.binarySearch(arraSingle, 1));
        Assert.assertEquals(4, BinarySearch.binarySearch(arraSingle, 78));
        Assert.assertEquals(2, BinarySearch.binarySearch(arraSingle, 34));
        Assert.assertEquals(8, BinarySearch.binarySearch(arraSingle, 122));

        // 数据长度为双数
        int[] arraySouble = {1, 32, 34, 56, 78, 79, 89, 99, 122, 352};
        Assert.assertEquals(0, BinarySearch.binarySearch(arraySouble, 1));
        Assert.assertEquals(4, BinarySearch.binarySearch(arraySouble, 78));
        Assert.assertEquals(2, BinarySearch.binarySearch(arraySouble, 34));
        Assert.assertEquals(8, BinarySearch.binarySearch(arraySouble, 122));
        Assert.assertEquals(9, BinarySearch.binarySearch(arraySouble, 352));

        /**
         *  相同数查找
         *  1, 32, 32, 56, 78, 89, 89, 89, 122
         *  0	1	2	3	4	5	6	7	8
         */
        int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};
        Assert.assertEquals(6, BinarySearch.binarySearch(arrayExistSameValue, 89));

        /**
         *  相同数查找
         *  1, 32, 32, 32, 86
         *  0	1	2	3	4
         */
        int[] arrayExistSameValue2 = {1, 32, 32, 32, 86};
        Assert.assertEquals(2, BinarySearch.binarySearch(arrayExistSameValue2, 32));


        // 不存在数查找
        int[] arraySouble2 = {1, 32, 34, 56, 78, 79, 89, 99, 122, 352};
        Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, 2));
        Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, -1));
        Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, Integer.MAX_VALUE));
        Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, 70));
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    lower_bound

        /**
     * 返回第一个大于等于Value的值
     *
     * @param array
     * @param value
     * @return
     */
    public static int binarySearchLowerBound(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) {
                end = mid - 1;
            } else if (midValue < value) {
                start = mid + 1;
            } else { // ==
                end = mid - 1;
            }
        }
        return start;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    单元测试

       @Test
    public void binarySearchLowerBound() {
        /**
         *  相同数查找
         *  1, 32, 32, 56, 78, 89, 89, 89, 122
         *  0	1	2	3	4	5	6	7	8
         */
        int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};
        Assert.assertEquals(0, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 0));
        Assert.assertEquals(1, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 32));
        Assert.assertEquals(4, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 57));
        Assert.assertEquals(5, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 89));
        Assert.assertEquals(8, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 122));
        Assert.assertEquals(9, BinarySearch.binarySearchLowerBound(arrayExistSameValue, Integer.MAX_VALUE));

        int[] arrayExistSameValue2 = {1, 32, 32, 56, 90, 90, 90, 90, 122};
        Assert.assertEquals(4, BinarySearch.binarySearchLowerBound(arrayExistSameValue2, 90));
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    UpperBound

        /**
     * 返回第一个大于Value的值
     *
     * @param array
     * @param value
     * @return
     */
    public static int binarySearchUpperBound(int[] array, int value) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >>> 1;
            int midValue = array[mid];
            if (value < midValue) {
                end = mid - 1;
            } else if (midValue < value) {
                start = mid + 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    单元测试

    @Test
public void binarySearchUpperBound() {
    /**
     *  相同数查找
     *  1, 32, 32, 56, 78, 89, 89, 89, 122
     *  0  1  2  3  4  5  6  7  8
     */
    int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};
    Assert.assertEquals(0, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 0));
    Assert.assertEquals(3, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 32));
    Assert.assertEquals(4, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 57));
    Assert.assertEquals(8, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 89));
    Assert.assertEquals(9, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 122));
    Assert.assertEquals(9, BinarySearch.binarySearchUpperBound(arrayExistSameValue, Integer.MAX_VALUE));

    int[] arrayExistSameValue2 = {1, 1,1,1};
    Assert.assertEquals(4, BinarySearch.binarySearchUpperBound(arrayExistSameValue2, 1));
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    确定相同元素的个数

    @Test
public void testBinarySearchBoundEqualsNum() {
    /**
     *  相同数查找
     *  1, 32, 32, 56, 78, 89, 89, 89, 122
     *  0  1  2  3  4  5  6  7  8
     */
    int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};
    Assert.assertEquals(3, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 89)
            - BinarySearch.binarySearchLowerBound(arrayExistSameValue, 89));
    Assert.assertEquals(0, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 4)
            - BinarySearch.binarySearchLowerBound(arrayExistSameValue, 4));
    int[] arrayExistSameValue2 = {1, 1,1,1};
    Assert.assertEquals(4, BinarySearch.binarySearchUpperBound(arrayExistSameValue2, 1)
            - BinarySearch.binarySearchLowerBound(arrayExistSameValue, 1));

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
  • 相关阅读:
    spring boot加mybatis puls实现，在新增/修改时，对某些字段进行处理，使用的@TableField（）或者AOP @Before
    Mysql 45讲学习笔记（二十九）判断数据库是否可用
    EEG-fNIRS跨模态迁移学习优化BCI系统分类精度
    mock.js的使用
    【C++】循环体内和循环体外定义变量的区别
    坚忍型性格分析，坚忍型人格的职业发展
    ARM/DSP+FPGA运动控制机器视觉控制器方案定制
    NZ系列工具NZ02:VBA读取PDF使用说明
    带滚动字幕的视频批量制作的方法
    json数据刨根究底
  • 原文地址：https://blog.csdn.net/u014687242/article/details/132819451