二分查找基本原理
二分查找基本原理
- 1.二分查找
- 1.1 基本概念
- 1.2 二分查找查找步骤
- 1.2.1 中间索引不能整除,取整数作为中间索引
- 1.2.2 索引不能整除,整数+1作为中间索引
- 1.3 二分查找大O记法表示
- 2. 二分查找代码实现
1.二分查找
1.1 基本概念
- 二分法(折半查找)是一个查找算法
- 要求:数据必须是有序列表
- 核心思想:掐头结尾取中间
1.2 二分查找查找步骤
1.2.1 中间索引不能整除,取整数作为中间索引

1.2.2 索引不能整除,整数+1作为中间索引

1.3 二分查找大O记法表示
| 元素个数 | 步骤次数 |
|---|---|
| 2 | 1 |
| 4 | 2 |
| 8 | 3 |
| 16 | 4 |
| N | log2Nlog_2^{N}log2N |
- 二分查找大O记法表示:log2Nlog_2^{N}log2N
- 意味着该算法当数据量翻倍时,步数加 1。
2. 二分查找代码实现
# 方式一
lis = [1, 12, 14, 15, 23, 35, 435, 567, 578, 656, 789, 1234]
n = int(input('请输入你要查找的数:'))
left = 0
right = len(lis) - 1
while left <= right:middle = (left + right) // 2print(f"当前中间索引为{middle},值为{lis[middle]}")if n > lis[middle]:left = middle+1elif n < lis[middle]:right = middle-1else:print('找到了,他在索引为%s位置' % middle)break
else:print('没有这个数据')# 方式二
lis = [1, 12, 14, 15, 23, 35, 435, 567, 578, 656, 789, 1234]
n = int(input('请输入你要查找的数:'))
left = 0
right = len(lis) - 1
while left <= right:middle = (left + right) // 2if (left + right) % 2 != 0:middle = ((left + right) // 2)+1print(f"当前中间索引为{middle},值为{lis[middle]}")if n > lis[middle]:left = middle+1elif n < lis[middle]:right = middle-1else:print('找到了,他在索引为%s位置' % middle)break
else:print('没有这个数据')

相关文章:
二分查找基本原理
二分查找基本原理1.二分查找1.1 基本概念1.2 二分查找查找步骤1.2.1 中间索引不能整除,取整数作为中间索引1.2.2 索引不能整除,整数1作为中间索引1.3 二分查找大O记法表示2. 二分查找代码实现1.二分查找 1.1 基本概念 二分法(折半查找)是一…...
【Python实战案例】Python3网络爬虫:“可惜你不看火影,也不明白这个视频的分量......”m3u8视频下载,那些事儿~
前言 哈喽!上午好嘞,各位小可爱们!有没有等着急了呀~ 由于最近一直在学习新的内容,所以耽搁了一下下,抱歉.jpg 双手合十。 所有文章完整的素材源码都在👇👇 粉丝白嫖源码福利,请移…...
UE4:使用样条生成随机路径,并使物体沿着路径行走
一、关于样条的相关知识 参考自:样条函数 - 馒头and花卷 - 博客园 三次样条(cubic spline)插值 - 知乎 B-Spline(三)样条曲线的性质 - Fun With GeometryFun With Geometry 个人理解的也不是非常深,但是大概要知道的就是样条具…...
计算机组成原理(判断题)
计算机控制器是根据事先编好的程序,根据其指令来进行控制只会每一步骤的操作; 面向主存的双总线结构计算机系统,因在CPU与主存之间增加了一组存储器总线,由于通过存储器总线访存,提高了CPU的访存速度,也减轻…...
error: failed to push some refs to ... 就这篇,一定帮你解决
目录 一、问题产生原因 二、解决办法 三、如果还是出问题,怎么办?(必杀) 一、问题产生原因 当你直接在github上在线修改了代码,或者是直接向某个库中添加文件,但是没有对本地库同步,接着你想…...
DAMA数据管理知识体系指南之数据仓库和商务智能管理
第9章 数据仓库和商务智能管理 9.1简介 数据仓库(Data Warehouse,DW)由两个主要部分构成:首先是一个整合的决策支持数据库,其次是用于收集、清洗、转换、存储来自于各种操作型数据源和外部数据源数据的相关软件程序。两者结合以支持历史的、…...
PHP的五种常见设计模式
工厂模式 最初在设计模式 一书中,许多设计模式都鼓励使用松散耦合。要理解这个概念,让我们最好谈一下许多开发人员从事大型系统的艰苦历程。在更改一个代码片段时,就会发生问题,系统其他部分 —— 您曾认为完全不相关的部分中也有…...
教你搞懂线段树,从基础到提高
秋名山码民的主页 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 🙏作者水平有限,如发现错误,还请私信或者评论区留言! 目录前言线段树逻辑概念线段树的俩个重要用处代码实现线段树题目巩固最后…...
C语言进阶——自定义类型:结构体
🌇个人主页:_麦麦_ 📚今日名言:生活不可能像你想象的那么好,也不会像你想象的那么糟。——莫泊桑《羊脂球》 目录 一、前言 二、正文 1结构体 1.1结构体的基础知识 1.2结构的声明 1.3特殊的声明 1.4结构体变量的…...
SpringSecurity学习笔记01
目录 一、课程介绍 二、框架概述 三、入门案例 四、基本原理(过滤器链) 五、基本原理(过滤器加载过程) 六、基本原理(两个重要的接口) 七、web权限方案-用户认证(设置用户名密码上) 八、…...
Python语言零基础入门教程(十一)
Python 列表(List) 序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置,或索引,第一个索引是0,第二个索引是1,依此类推。 Python有6个序列的内置类型,但最常见的是列表和元组。 序列都可以…...
现货白银基础知识
任何活动,任何项目,任何工作都离不开基础知识,这是肯定的。万丈高楼平地起,要想要简称百层高楼,首先得把低级打好!现货白银投资也是一样的道理,现在我们就来一起聊聊现货白银基础知识的问题&…...
数据库原理及应用基础知识点
数据库原理基础知识点大全数据库原理及应用1、数据库系统概述1.1 基本概念1.2 数据模型1.3 数据库系统的结构2、实体 -- 联系模型2.1 基本概念2.2 实体-联系图2.3 弱实体集3、关系数据模型3.1 关系数据库的结构3.2 从ER模型到关系模型3.3 关系操作、完整性约束、关系代数4、关系…...
【数据结构】栈(stack)
写在前面本篇文章开始讲解栈的有关知识,其实把顺序表和链表学好,那么这一章便不在话下,栈实际上就是顺序表或链表的一些特殊情况。用顺序表实现的栈叫做顺序栈用链表实现的栈叫做链栈文章的内容分为几个部分,希望读者能快速了解文…...
初识shell
文章目录一、shell基本知识1.1为什么学习和使用Shell编程1.2 什么是Shell1.2.1 shell的起源1.2.2 shell的功能1.3 shell的分类1.4 作为程序设计的语言——shell1.5 如何学好shell1.6 shell脚本的基本元素1.7 shell脚本编写规范1.8shell脚本的执行方式1.9 执行脚本的方法1.10 sh…...
程序员如何编写好开发技术文档 如何编写优质的API文档工作
编写技术文档,是令众多开发者望而生畏的任务之一。它本身是一件费时费力才能做好的工作。可是大多数时候,人们却总是想抄抄捷径,这样做的结果往往非常令人遗憾的,因为优质的技术文档是决定你的项目是否引人关注的重要因素。无论开…...
二级C语言操作例题(四十)
一、程序填空题 在此程序中,函数fun的功能是:在形参s所指字符串中寻找与参数c相同的字符,并在其后插入一个与之相同的字符,若找不到相同的字符则不做任何处理。 例如,若s所指字符串”baacda”,中c的字符为…...
vue-router 源码解析(二)-创建路由匹配对象
文章目录基本使用导语createRouterMatcher 创建匹配路由记录addRoute 递归添加matchercreateRouteRecordMatcher 创建matchertokenizePath 解析pathtokensToParser 记录打分insertMatcher 将matcher排序总结基本使用 const routes [{path:"/",component: Demo2,nam…...
分布式新闻项目实战 - 10.Long类型精度丢失问题
怒发冲冠,凭阑处、潇潇雨歇。抬望眼,仰天长啸,壮怀激烈。三十功名尘与土,八千里路云和月。莫等闲、白了少年头,空悲切。 靖康耻,犹未雪。臣子恨,何时灭。驾长车,踏破贺兰山缺。壮志饥…...
如何将本地jar包安装到maven仓库
mvn install:install-file:主要是将本地自定义jar安装到maven仓库,然后在pom中可以直接通过dependency的方式来引用。 此命令有如参数: 命令说明-DgroupId自定义groupId设置groupId 名-DartifactId自定义artifactId设置该包artifactId名-Dversion自定义…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
负载均衡器》》LVS、Nginx、HAproxy 区别
虚拟主机 先4,后7...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
