【二分查找法及其应用】
文章目录
- 一. 前提
- 二. 基本思路
- 三. 代码实现
- 四. 封装在STL中的二分查找算法
- 五. 浮点数二分
一. 前提
- 待查找的序列是有序的;
- 待查找的 a 采取顺序存储结构。
二. 基本思路
设在升序序列 a [ low…high ] 查找的 k ,
首先找中间值 mid= a [ ( low+high )/2 ] ;
然后比较 k 和 a [ mid ] , 分成三个情况:
(1)k == a[ mid ] , 直接返回 a [ mid ] ;
(2)k < a [ mid ] , 新的查找区域变为左子表 a [ low , mid-1 ] ;
(3)k > a [ mid ] , 新的查找区域变为右子表 a [ mid+1 , high ] ;
下一次查找根据 新的查找区间 进行查找。
三. 代码实现
//二分查找法
int BinSearch(int a[],int low,int high,int k)
{if(low<=high){ //当前区间存在元素 int mid=(low+high)/2;if(a[mid]==k)return mid; //找到后返回其下标 if(a[mid]<k)return BinSearch(int a[],int low,int mid-1,int k);if(a[mid]>k)return BinSearch(int a[],int mid+1,int high,int k);}else{return -1; //区间不存在元素,返回 -1 }
}
可见二分查找的时间重要花费在元素比较上,其时间复杂度为O(log2n\log_{2}nlog2n)
四. 封装在STL中的二分查找算法
- lower_bound
ForwoardIterator lower_bound( ForwoardIterator begin , ForwoardIterator end , const T& num)
lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
- upper_bound
ForwoardIterator upper_bound( ForwoardIterator begin , ForwoardIterator end , const T& num)
upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
- binary_search
bool binary_bound( ForwoardIterator begin , ForwoardIterator end , const T& num)
区间中存在要查找的值,返回 true ;否则, false
五. 浮点数二分
1.求n的平方根,保留6位小数
#include<bits/stdc++.h>
using namespace std;int main()
{double n;cin>>n;double l=0,r=n;while(r-l>=1e-8){ //负的,别忘!!!double mid=(l+r)/2;if(mid*mid>n) r=mid;else l=mid;}printf("%lf",l);return 0;}
相关文章:
【二分查找法及其应用】
文章目录一. 前提二. 基本思路三. 代码实现四. 封装在STL中的二分查找算法五. 浮点数二分一. 前提 待查找的序列是有序的;待查找的 a 采取顺序存储结构。 二. 基本思路 设在升序序列 a [ low…high ] 查找的 k , 首先找中间值 mid a [ ( lowhigh )/2 …...
Android 进阶——Framework核心 之Binder Java成员类详解(三)
文章大纲引言一、Binder Java家族核心成员关系图二、Binder Java家族核心成员源码概述1、android.os.IBinder1.1、boolean transact(int code, Parcel data, Parcel reply, int flags) send a call to an IBinder object1.2、String getInterfaceDescriptor()1.3、boolean ping…...
Maven
Maven 1.什么是Maven 官方网站 https://maven.apache.org/ Maven是一款服务于Java平台的自动化构建工具,它可以帮助我们更方便的对项目进行构建、管理项目jar包 ,包括: bulid 项目,切换 jar 版本,添加 jar, 删除 jar 包等 1.…...
1947抓住那头牛(队列 广度优先搜索)
目录 题目描述 解析 解题思路 代码部分 代码部分 运行结果 看看len数组中各个位置的标记值 为什么这样做一定是最短路径: 题目描述 农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<N<100000)&…...
基于linux5.15.5的IMX 参考手册 ---21
基于linux5.15.5的IMX 参考手册 — 21 10.5.2高清多媒体接口(HDMI)和显示端口(DP)概述 10.5.2.1测试名称 •mxc_cec_test.out 10.5.2.1.1位置 /unit_tests/HDMI/ 10.5.2.1.2功能 验证HDMI CEC功能并向HDMI接收器发送断电命令。 1…...
Android Dalvik虚拟机 堆初始化流程
前言 上篇文章介绍了dalvik虚拟机启动流程,在dalvik虚拟机启动时调用了dvmGcStartup来启动堆。 本文介绍我们在日常开发使用Java时的堆创建流程。 Dalvik堆介绍 Dalvik虚拟机中,堆是由heap[0] Active堆和heap[1] Zygote堆两部分组成的。其中ÿ…...
0讲(补)——开发前必备基本常识
前言 专栏内容持续补充更新,目前正在进行优惠活动 目录 前言 一、函数的声明和定义 二、预编译 三、串口打印中的printf函数的使用...
JS学习笔记
1.WebAPIs简介导读Web APIs 和JS 基础关联性JS 基础阶段以及 Web APIs 阶段JS基础学习 ECMAScript 基础语法为后面作铺垫,Web APIs 是JS 的应用,大量使用JS基础语法做交互效果①JS 基础阶段我们学习的是ECMAScript 标准规定的基本语法要求同学们掌握JS 基…...
linux005之用户、组管理
linux用户管理简介: 任何使用linux系统的用户,都必须使用一个合法的账号和密码,账号和密码一般都是超级管理员创建,当然普通用户也可以创建用户,前提是必须拥有创建用户权限。 root是linux系统中默认创建的超级用户 创…...
列线图工具_Nomogram
定义 列线图是一种相对传统的分析方法,用于展示自变量和因变量的线性关系,及其特征的重要程度。 现在用SHAP,和机器学习库中的 Feature importance 工具可以实现类似甚至更好效果。不过很多传统的研究领域比较认这种方法。 列线图工具建立在…...
【C++】类和对象(一)
目录一、面向过程和面向对象初步认识二、类的引入三、类的定义四、类的访问限定符及封装4.1、访问限定符4.2、封装五、类的作用域六、类的实例化七、类对象的大小八、this指针8.1、this指针的引出8.2、this指针的特性8.3、C语言和C实现Stack的对比一、面向过程和面向对象初步认…...
Python获取搜索引擎结果
前言 想快速获取各个高校的博士招生网站,于是通过python先获取出有可能包含高校博士招生网站的URL,然后通过人为筛选得到了想要的招生网站(注意,并非直接爬取,是间接获取的)。 整理了一份网站名单&#x…...
2.4.8 PCIe——物理逻辑层——REFCLK
一、概述 pcie的参考时钟由板级输入,提供给IP内PHY层的PLL使用,由PLL产生core_clk和pipe_clk。 二、REFCLK产生方式 Serdes 所用时钟由 PHY 模块内的PLL生成,PLL的参考时钟可以由common clock(外部背板提供)、separ…...
树莓派4B arm64 搭建 docker+drone+gitea
树莓派4B arm64 搭建 dockerdronegitea 记录时间: 2023年02月10日 树莓派烧录 如何用树莓派搭建一台永久运行的个人服务器? https://mp.weixin.qq.com/s?__bizMzI5NjA0ODkwNA&mid2651847658&idx1&sn267a1257b43d4a76f2a081ed157b77f9&chksmf7b11…...
Java的JDBC编程
目录 1. 打开IDEA,新建Project 2. 引入依赖 (1)下载驱动包 (2)将驱动包导入Project 3. 编写代码 (1)创建数据源 (2)让代码和数据库服务器建立联系 (3&…...
CSS:块格式化上下文(BFC)
块格式化上下文是块级盒子的布局过程发生的区域,也是浮动元素与其他元素交互的区域。 块格式化上下文(BFC)的创建 满足以下条件将创建块格式化上下文: 根元素()浮动元素(float 值不为 none)绝对定位元素…...
paddle表情识别部署
表情识别模块1.环境部署1.1同样采用fastDeploy库1.2相关模型2.封装成静态库2.1参考[百度Paddle中PP-Mattingv2的部署并将之封装并调用一个C静态库](https://blog.csdn.net/weixin_43564060/article/details/128882099)2.2项目依赖添加2.3生成成功3.test3.1创建emotion_test项目…...
Python-第五天 Python函数
Python-第五天 Python函数一、函数介绍1. 什么事函数二、函数的定义1.函数的定义:2.案例三、函数的参数1.函数的传入参数2.案例升级四、函数的返回值1.什么是返回值2.返回值的语法3.None类型4.None类型的应用场景五、函数说明文档1.函数的说明文档2.在PyCharm中查看…...
【Python学习笔记】28.Python3 错误和异常
前言 作为 Python 初学者,在刚学习 Python 编程时,经常会看到一些报错信息,在前面我们没有提及,这章节我们会专门介绍。 Python3 错误和异常 Python 有两种错误很容易辨认:语法错误和异常。 Python assert…...
SQLServer 迁移到 MySQL 工具对比
我之所以会写这篇对比文章,是因为公司新产品研发真实经历过这个痛苦过程(传统基于 SQL Server开发的C/S 产品转为 MySQL云产品)。首次需要数据转换是测试环节,当时为了快速验证新研发云产品性能与结果准确性(算法类&am…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
