数据结构与算法系列-二分查找
二分查找
什么是二分查找?
二分查找是一种针对有序集合,每次将要查找的区间缩小一半,直到找到查找元素,或区间被缩小为0。
如何实现二分查找?
实现有3个注意点:
- 终止条件是 low <= high
2.求中点的算法是 low + (high - low)/2
3.low和high的更新是low=mid+1 即到更大的区间找, high=mid-1 即到更小的区间找。
非递归实现
// 终止条件low>=high 当low=high时,mid=low+(high-low)/2=low=high,即没有等号将少比较一个点// 中点 mid = low + (high-low)/2 即以low为起点,计算low和high之间的中点// mid<value 找大区间 low=mid+1,mid>value,找小区间,high=mid-1public int binSearch(int[] arr,int n,int value){int low=0;int high=n-1;while(low<=high){int mid=low+((high-low)>>1);//int mid=low+(high-low)/2;if(arr[mid]<value){low=mid+1;} else if(arr[mid]>value){high=mid-1;} else{return mid;}}return -1;}
递归实现
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {return bsearchInternally(a, 0, n - 1, val);
}private int bsearchInternally(int[] a, int low, int high, int value) {if (low > high) return -1;int mid = low + ((high - low) >> 1);if (a[mid] == value) {return mid;} else if (a[mid] < value) {return bsearchInternally(a, mid+1, high, value);} else {return bsearchInternally(a, low, mid-1, value);}
}
二分查找有哪些局限性?
1. 二分查找依赖的是顺序表结构,也就是数组
2. 二分查找要求数据有序
3. 数据量太小不适合二分查找,除非每个数据的操作非常耗时,比如,数组中存储的都是长度超过 300 的字符串,如此长的两个字符串之间比对大小,就会非常耗时。
4. 数据量太大也不适合二分查找,因为数组需要占用大量连续的空间
5. 动态数据不适合二分查找,频繁的插入和删除在数组结构下效率很低
思考题
- 如何编程实现“求一个数的平方根”?要求精确到小数点后 6 位。
可以用牛顿弦切法来求平方跟
double number = 2; //待求平方根的数
double xini = 10;//初始点
while(xinixini - number > 1e-6) {
xini = (number + xinixini)/2/xini;
}
// xini为平方根 - 我刚才说了,如果数据使用链表存储,二分查找的时间复杂就会变得很高,那查找的时间复杂度究竟是多少呢?
链表不像数组那样支持随机访问,所以链表主要花的是查找第n个节点的访问的时间。
第一次需要遍历n/2个节点,
第二次需要遍历n/4个节点,
第三次需要遍历n/8个节点,
n/2 + n/4 + n/8 + …
和约等于n,因此算法复杂度为O(n),单考虑到其他二分查找的额外操作,会比直接遍历循环查找慢一些。
二分查找有哪些变体问题?
对于有序数组中有重复元素而言二分查找通常有以下4个变体问题。
查找第一个值等于给定值的元素
查找最后一个值等于给定值的元素
查找第一个大于等于给定值的元素
查找最后一个小于等于给定值的元素
这些都是查找等于给定值的变体问题,想一想,你有什么思路可以实现呢?
如何实现变体的二分查找?
arr[mid]和value的值的比较有三种情况:大于,小于,等于
那对于问题1和2而言我们要特殊处理的等于的情况,
问题3要特殊处理大于等于的情况,
问题4要特殊处理小于等于的情况。
问题1的特殊处理逻辑:
等于的情况下,我们mid的下标有可能是0,即数组的第一个元素,那么我们直接返回mid就好了,
那其余情况就是mid>0,那么我们就看mid的前一个元素是否等于value,如果不等于,说明mid是第一个等于value的元素,也直接返回,
如果等于mid,那么我们就需要在前面的区间去查找了,即 high = mid - 1;
那问题2,3,4和1的处理思路类似,可以试着自己实现。
1
public int binSearchFirst(int[] arr,int n,int value){int low=0;int high=n-1;while (low<=high) {int mid = low + (high - low) / 2;if(arr[mid]<value){low=mid+1;} else if(arr[mid]>value){high=mid-1;} else{// 需要特殊处理的是等于的情况// 1.看mid是否为第一个元素,是返回mid// 2.看mid的前一个元素是否等于value,不等于返回mid// 3.mid的前一个元素等于value,那么就应该去前面区间找,即 high = mid - 1;if(mid==0||arr[mid-1]!=value) {return mid;}high=mid-1;}}return -1;}
2
public int binSearchFirst(int[] arr,int n,int value){int low=0;int high=n-1;while (low<=high) {int mid = low + (high - low) / 2;if(arr[mid]<value){low=mid+1;} else if(arr[mid]>value){high=mid-1;} else{// 需要特殊处理的是等于的情况// 1.看是mid否为最后一个元素,是返回mid// 2.看mid的后一个元素是否等于value,不等于返回mid// 3.mid的后一个元素等于value,那么就应该去后面区间找,即 low = mid + 1;if(mid==n-1||arr[mid+1]!=value) {return mid;}low=mid+1;}}return -1;}
3
public int binSearchFirst(int[] arr,int n,int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] >= value) {// 主要处理大于等于的情况// 1.看mid是否为第一个元素,是返回mid// 2.看mid的前一个元素是否小于value,是返回mid// 3.前一个元素大于等于value,应该去前面区间找,即high=mid-1if(mid==0||arr[mid-1]<value){return mid;}high = mid - 1;} else {low = mid + 1;}}return -1;}
4
public int binSearchFirst(int[] arr,int n,int value) {int low = 0;int high = n - 1;while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] <= value) {// 主要处理大于等于的情况// 1.看mid是否为最后一个元素,是返回mid// 2.看mid的后一个元素是否大于value,是返回mid// 3.后一个元素小于等于value,应该去后面区间找,即low=mid+1if(mid==n-1||arr[mid+1]>value){return mid;}low = mid + 1;} else {high = mid - 1;}}return -1;}
二分查找的实际应用场景?
绝大部分情况能用二分查找解决的问题我们更倾向使用散列表或二叉查找树,
那二分查找其实更适用于近似的查找(范围查找)问题,因为这类问题用上述数据结构都不容易实现。
思考题
我们今天讲的都是非常规的二分查找问题,今天的思考题也是一个非常规的二分查找问题。如果有序数组是一个循环有序数组,比如 4,5,6,1,2,3。针对这种情况,如何实现一个求“值等于给定值”的二分查找算法呢?
我们发现循环数组存在一个性质:以数组中间点为分区,会将数组分成一个有序数组和一个循环有序数组。
如果首元素小于 mid,说明前半部分是有序的,后半部分是循环有序数组;
如果首元素大于 mid,说明后半部分是有序的,前半部分是循环有序的数组;
如果目标元素在有序数组范围中,使用二分查找;
如果目标元素在循环有序数组中,设定数组边界后,使用以上方法继续查找。
时间复杂度为 O(logN)。
相关文章:
数据结构与算法系列-二分查找
二分查找 什么是二分查找? 二分查找是一种针对有序集合,每次将要查找的区间缩小一半,直到找到查找元素,或区间被缩小为0。 如何实现二分查找? 实现有3个注意点: 终止条件是 low < high 2.求中点的算…...
CSS 毛玻璃特效运用目录
主要是记录毛玻璃相关的特效实践案例和实现思路。 章节名称完成度难度文章地址完整代码下载地址Glassmorphism 登录表单完成一般文章链接代码下载Glassmorphism 按钮悬停效果完成一般文章链接代码下载Glassmorphism 计算器完成一般文章链接代码下载Glassmorphism 卡片悬停效果…...

如何在Qt6中引入Network模块
2023年10月1日,周日凌晨 2023年10月2日,周一下午 第一次更新 目录 如果用的是CMakeQt Console ApplicationQt Widgets Application如果用的是qmake 如果用的是CMake find_package(Qt6 COMPONENTS Network REQUIRED) target_link_libraries(mytarget…...

2023/10/4 QT实现TCP服务器客户端搭建
服务器端: 头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTcpServer> #include <QTcpSocket> #include <QList> #include <QMessageBox> #include <QDebug>QT_BEGIN_NAMESPACE namespace Ui { cla…...

云原生边缘计算KubeEdge安装配置
1. K8S集群部署,可以参考如下博客 请安装k8s集群,centos安装k8s集群 请安装k8s集群,ubuntu安装k8s集群 2.安装kubEedge 2.1 编辑kube-proxy使用ipvs代理 kubectl edit configmaps kube-proxy -n kube-system #修改kube-proxy#大约在40多行…...

【LeetCode热题100】--35.搜索插入位置
35.搜索插入位置 使用二分查找: class Solution {public int searchInsert(int[] nums, int target) {int low 0,high nums.length -1;while(low < high){//注意每次循环完都要计算midint mid (low high)/2;if(nums[mid] target){return mid;}if(nums[mid]…...

mysql面试题13:MySQL中什么是异步复制?底层实现?
该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:讲一讲mysql中什么是异步复制?底层实现? MySQL中的异步复制(Asynchronous Replication)是一种复制模式,主服务器将数据写入二进制日志后,无…...

SpringBoot-Shiro安全权限框架
Apache Shiro是一个强大而灵活的开源安全框架,它干净利落地处理身份认证,授权,企业会话管理和加密。 官网: http://shiro.apache.org/ 源码: https://github.com/apache/shiro Subject:代表当前用户或…...
PostgreSQL基础语法
当谈到关系型数据库管理系统(RDBMS)时,PostgreSQL是一个备受推崇的选择。它是一个开源的、强大的RDBMS,具有广泛的功能和支持。本文将介绍一些PostgreSQL的基础语法,以帮助您入门。 1. 安装和配置 在开始使用PostgreS…...
编程前置:处理Excel表格,定位单元格位置,输入文字前,让AI机器人知道我说什么
原提问: input输入表头 (input内除了/,空格 回车 标点符号等 全部作为单元格分隔符) 由我设置input输入的是行or列 给选项 1. 行 2. 列 默认回车或没输入值是列由我设置起始位置行列 例如 3,2 表示3行2列 当我输入3,2 就表示在第…...

Linux基本指令介绍系列第四篇
文章目录 前言一、Linux基本指令介绍1、more指令2、less指令3、head指令4、tail指令5、bc指令6、管道文件介绍7、与时间相关的指令 总结 前言 本文介绍Linux使用时的部分指令,读者如果想了解更多基本指令的使用,可以关注博主的后续的文章。 博主使用的实…...
读取vivo手机截图尺寸移动.jpg等文件
这个代码的设计初衷是为了解决图片处理过程中的一些痛点。想象一下,我们都曾遇到过这样的情况:相机拍摄出来的照片、网络下载的图片,尺寸五花八门,大小不一。而我们又渴望将它们整理成一套拥有统一尺寸的图片,让它们更…...
Web前端-Vue2+Vue3基础入门到实战项目-Day2(指令补充, computed计算属性, watch侦听器, 水果购物车)
Web前端-Vue2Vue3基础入门到实战项目-Day2 指令补充指令修饰符v-bind 对样式控制的增强控制class案例 - 京东秒杀tab导航高亮控制style案例 - 控制进度条 v-model 应用于其他表单元素 computed计算属性基本使用computed计算属性 vs methods方法计算属性完整写法案例 - 成绩 wat…...

ffmpeg之去除视频水印
ffmpeg去除水印使用delogo视频滤镜。 delogo参数: x,y,w,h分别表示logo区域的左上角位置及宽度和高度; show:0表示不显示logo区域,1表示显示logo区域。 执行下面的命令: ffmpeg -i 1.mp4 -vf delogox300:y10:w80:h30:show0 out.mp4 效果…...

第二章 线性表
线性表 线性表的基本概念线性表的顺序存储线性表顺序存储的类型定义线性表基本运算在顺序表上的实现顺序表实现算法的分析 线性表的链接存储单链表的类型定义线性表的基本运算在单链表上的实现 其他运算在单链表上的实现建表删除重复结点 其他链表循环链表双向循环链表 顺序实现…...
Java 超高频常见字符操作【建议收藏】
文章目录 前言1. 字符串拼接2. 字符串查找3. 字符串截取4. 字符串替換5. 字符串分割6. 字符串比较7. 字符串格式化8. 字符串空格处理 总结 前言 为了巩固所学的知识,作者尝试着开始发布一些学习笔记类的博客,方便日后回顾。当然,如果能帮到一…...

MongoDB数据库网站网页实例-编程语言Python+Django
程序示例精选 PythonDjangoMongoDB数据库网站网页实例 如需安装运行环境或远程调试,见文章底部个人QQ名片,由专业技术人员远程协助! 前言 这篇博客针对《PythonDjangoMongoDB数据库网站网页实例》编写代码,代码整洁,…...

开箱报告,Simulink Toolbox库模块使用指南(七)——S-Fuction Builter模块
S-Fuction Builter S-Fuction Builter模块,Mathworks官方Help对该部分内容的说明如下所示。 DFT算法的原理讲解和模块开发在前几篇文章中已经完成了,本文介绍如何使用S-Fuction Builter模块一步到位地自动开发DFT算法模块,包括建立C MEX S-Fu…...
spring-boot 操作 mongodb 数据库
如何使用 spring-boot 操作 mongodb 数据库 配置文件: spring:data:mongodb:host: 127.0.0.1database: fly_articleDbport: 27017# 可以采取 mysql 写法# uri: mongodb://127.0.0.1/fly_articleDb依赖信息: <?xml version"1.0" encoding"UTF-…...

JVM篇---第三篇
系列文章目录 文章目录 系列文章目录一、什么是Java虚拟机?为什么Java被称作是“平台无关的编程语言”?二、Java内存结构三、说说对象分配规则一、什么是Java虚拟机?为什么Java被称作是“平台无关的编程语言”? Java虚拟机是一个可以执行Java字节码的虚拟机进程。Java源文…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...