【算法】查找类——二分查找算法
二分查找算法算法总结
算法描述
该算法属于查找算法。当需要从有序数组中查找某一元素时,可以使用该算法进行查找。(本文章假设数组是升序排列的数组)
算法思想
每次进行对半查找,获取中间元素值,然后与目标值进行比较。
- 如果目标元素等于中间值,则查找成功,返回中间元素的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));}
相关文章:
【算法】查找类——二分查找算法
二分查找算法算法总结 算法描述 该算法属于查找算法。当需要从有序数组中查找某一元素时,可以使用该算法进行查找。(本文章假设数组是升序排列的数组) 算法思想 每次进行对半查找,获取中间元素值,然后与目标值进行…...
Ansible FIle模块,使用Ansible File模块进行文件管理
当使用 Ansible 进行自动化配置和管理时,file 模块是一个强大的工具,用于在目标主机上创建、修改和删除文件和目录。它提供了一种简单而灵活的方式来处理文件系统操作。在本文中,我们将详细介绍如何使用 Ansible 的 file 模块。 1. 创建文件 …...

索尼mp4变成rsv修复案例(ILME-FX3)
索尼mp4的修复案例讲过很多,这次是索尼的ILME-FX3也算是一个畅销的机型,一般索尼没有封装的文件是RSV文件,但是极少遇到有多个RSV文件的,下边我们来讲下这个特殊案例。 故障文件:4个RSV文件,大小在1.78G~28G多 故障现…...

抓拍摄像机开关量控制4K高清手机远程看图建筑生长定时缩时相机
作为物联网数据采集解决方案专业提供商,数采物联网小编daq-iot 在这里做以下内容介绍,并诚挚的欢迎大家讨论和交流。 项目案例参考视频: https://www.bilibili.com/video/BV1Kp4y1T7wQ/?spm_id_from333.999.0.0 4K高清太阳能供电定时拍照相机,通过光…...
c++使用http请求-drogon框架
创建drogon框架 drogon_ctl create project test_ctrl添加一个控制器 进入controllers目录下 drogon_ctl create controller -h check_ctrl编写主函数 #include <drogon/drogon.h> int main() {//Set HTTP listener address and port//drogon::app().addListener("…...
幼儿棒球运动宣传介绍·野球6号位
幼儿棒球运动宣传介绍 1. 棒球对幼儿成长的重要性 棒球运动对幼儿协调能力和团队协作的培养 棒球运动对幼儿协调能力和团队协作的培养非常重要。通过棒球运动,孩子们可以学习如何与队友合作,如何在压力下保持冷静,以及如何快速做出决策。这…...

grpc多语言通信之GO和DART
都是一个吗生的,找下例子 上一篇文章说到go实现的grpc方法已经实现了一个grpc的server端, 注意: 这两个项目的.proto文件应当是完全一致的,只是方法用各自的语言实现罢了 报错了: Caught error: gRPC Error (code: 12, codeName: UNIMPLEMENTED, message: grpc: Decompresso…...

基于FPGA的RGB图像转Ycbcr实现,包括tb测试文件以及MATLAB辅助验证
目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 将FPGA的数据导入到matlab进行显示 2.算法运行软件版本 Vivado2019.2 matlab2022a 3.部分核心程序 timescale 1ns / 1ps // // Company: // E…...
centos 编译安装的php多版本 切换
centos 编译安装的php多版本 切换 wheris php php: /usr/bin/php /usr/lib64/php /etc/php.ini /etc/php.d /usr/local/php /usr/local/php7.4 /usr/share/php /usr/share/man/man1/php.1.gz/usr/bin/php: php可执行脚本,任何版本的php 通过软连接到这可以实现全局…...

Unity 性能优化之Shader分析处理函数ShaderUtil.HasProceduralInstancing: 深入解析与实用案例
Unity 性能优化之Shader分析处理函数ShaderUtil.HasProceduralInstancing: 深入解析与实用案例 点击封面跳转到Unity国际版下载页面 简介 在Unity中,性能优化是游戏开发过程中非常重要的一环。其中,Shader的优化对于游戏的性能提升起着至关重要的作用。…...

2023数学建模国赛E题黄河水沙监测数据分析完整代码分析+处理结果+思路文档
已经写出国赛E题黄河水沙监测数据分析完整代码分析处理结果思路分析(30页),包括数据预处理、数据可视化(分组数据分布图可视化、相关系数热力图可视化、散点图可视化)、回归模型(决策树回归模型、随机森林回…...
玩转Mysql系列 - 第19篇:游标详解
这是Mysql系列第19篇。 环境:mysql5.7.25,cmd命令中进行演示。 代码中被[]包含的表示可选,|符号分开的表示可选其一。 需求背景 当我们需要对一个select的查询结果进行遍历处理的时候,如何实现呢? 此时我们需要使…...

【量化分析】Python 布林线( Bollinger)概念
一、说明 布林线(BOLL),Bollinger Bands,利用统计原理,求出股价的标准差及其信赖区间,从而确定股价的波动范围及未来走势,利用波带显示股价的安全高低价位,因而也被称为布林带。 二、布林带基本概念 布林线…...

MySQL的权限管理与远程访问
MySQL的权限管理 1、授予权限 授权命令: grant 权限1,权限2,…权限n on 数据库名称.表名称 to 用户名用户地址 identified by ‘连接口令’; 该权限如果发现没有该用户,则会直接新建一个用户。 比如 grant select,insert,delete,drop on atguigudb.…...

在Qt创建的UI中放一个显示点云的窗口(PCL+QT5)
1、首先在Qt Designer创建UI后,拖一个Widget窗口出来 2、在对象查看器中右击该Widget,选择提升窗口部件,如下操作: 3、把UI转出来放在VS项目中,其中你的UI代码头文件会自带QVTKOpenGLNativeWidget.h,当然你…...
element ui el-table分页多选功能
selection-change:当选择项发生变化时会触发该事件(当分页切换时,选中的数据都会自动清空) 一、在el-table中添加 :row-key“id” <el-table :data"tableData" border style"width: 95%" selection-change…...
理解网络通信的基础:OSI七层模型与TCP/IP五层模型
在今天的数字化世界中,网络通信已经成为我们日常生活和商业活动的重要组成部分。为了更好地理解和管理网络通信,网络工程师和管理员使用不同的模型来组织和解释网络协议和通信过程。本文将介绍两种最重要的网络模型:OSI七层模型和TCP/IP五层模…...

Python爬虫-爬取文档内容,如何去掉文档中的表格,并保存正文内容
前言 本文是该专栏的第58篇,后面会持续分享python爬虫干货知识,记得关注。 做过爬虫项目的同学,可能或多或少爬取过文档数据,比如说“政务网站,新闻网站,小说网站”等平台的文档数据。爬取文档数据,笔者这里就不过多详述,而本文,笔者将主要介绍在爬取文档数据的过程中…...

【使用Cpolar和Qchan搭建自己的个人图床】
文章目录 前言1. Qchan网站搭建1.1 Qchan下载和安装1.2 Qchan网页测试1.3 cpolar的安装和注册 2. 本地网页发布2.1 Cpolar云端设置2.2 Cpolar本地设置 3. 公网访问测试总结 前言 图床作为云存储的一项重要应用场景,在大量开发人员的努力下,已经开发出大…...
flutter解决多个类名重名问题
Try using ‘as prefix’ for one of the import directives, or hiding the name from all but one of the imports. Flutter遇到这种错误,意思是你自己的import的库的类名跟一另一个导入的库,或者系统的类名名字相同.解决方法,把自己的一个类名用as 加一个前缀,使用的时候 用…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...

【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...