当前位置： 首页 > news >正文

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

news 2025/7/13 9:48:10

二分查找算法算法总结

算法描述

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

算法思想

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

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

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

接口定义

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

代码实现

闭合区间实现方案

/*** 标准二分查找法, 在一个数据找找寻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;
}

半闭合区间实现

/*** 标准二分查找法, 在一个数据找找寻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;
}

两个方案总结

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

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

例子：在同一数组中查找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));

二分查找算法拓展一 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;}

  • 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*/

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;elsereturn mid; // key found}return -(low + 1);  // key not found. // low 表示第一个大于key的元素}

代码实现

默认实现

    /*** 标准二分查找法, 在一个数据找找寻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;}

单元测试

    @Testpublic void testBinarySearch() {// 数据长度为单数 9int[] 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));}

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;}

单元测试

   @Testpublic 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));}

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;}

单元测试

@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));
}

确定相同元素的个数

@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));}
http://www.lryc.cn/news/163962.html

相关文章：

  • Ansible FIle模块，使用Ansible File模块进行文件管理
  • 索尼mp4变成rsv修复案例(ILME-FX3)
  • 抓拍摄像机开关量控制4K高清手机远程看图建筑生长定时缩时相机
  • c++使用http请求-drogon框架
  • 幼儿棒球运动宣传介绍·野球6号位
  • grpc多语言通信之GO和DART
  • 基于FPGA的RGB图像转Ycbcr实现,包括tb测试文件以及MATLAB辅助验证
  • centos 编译安装的php多版本 切换
  • Unity 性能优化之Shader分析处理函数ShaderUtil.HasProceduralInstancing: 深入解析与实用案例
  • 2023数学建模国赛E题黄河水沙监测数据分析完整代码分析+处理结果+思路文档
  • 玩转Mysql系列 - 第19篇：游标详解
  • 【量化分析】Python 布林线（ Bollinger）概念
  • MySQL的权限管理与远程访问
  • 在Qt创建的UI中放一个显示点云的窗口（PCL+QT5）
  • element ui el-table分页多选功能
  • 理解网络通信的基础：OSI七层模型与TCP/IP五层模型
  • Python爬虫-爬取文档内容，如何去掉文档中的表格，并保存正文内容
  • 【使用Cpolar和Qchan搭建自己的个人图床】
  • flutter解决多个类名重名问题
  • 微信小程序 按钮颜色
  • 【云原生】kubectl常用命令大全
  • git pull
  • C++学习之运算符与表达式
  • vue使用谷歌地图实现地点查询
  • 前端该了解的网络知识
  • python3在虚拟环境实用vscode调试错误输出ModuleNotFoundError: No module named ‘django‘解决方法
  • 如何获得一个Oracle 23c免费开发者版
  • 机器学习策略二——优化深度学习系统
  • Pytorch Advanced(三) Neural Style Transfer
  • 英飞凌TC3xx--深度手撕HSM安全启动(三)--TC3xx HSM系统架构