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

二分查找基本原理

二分查找基本原理

  • 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记法表示

元素个数步骤次数
21
42
83
164
Nlog2Nlog_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 中间索引不能整除&#xff0c;取整数作为中间索引1.2.2 索引不能整除&#xff0c;整数1作为中间索引1.3 二分查找大O记法表示2. 二分查找代码实现1.二分查找 1.1 基本概念 二分法(折半查找&#xff09;是一…...

【Python实战案例】Python3网络爬虫:“可惜你不看火影,也不明白这个视频的分量......”m3u8视频下载,那些事儿~

前言 哈喽&#xff01;上午好嘞&#xff0c;各位小可爱们&#xff01;有没有等着急了呀~ 由于最近一直在学习新的内容&#xff0c;所以耽搁了一下下&#xff0c;抱歉.jpg 双手合十。 所有文章完整的素材源码都在&#x1f447;&#x1f447; 粉丝白嫖源码福利&#xff0c;请移…...

UE4:使用样条生成随机路径,并使物体沿着路径行走

一、关于样条的相关知识 参考自&#xff1a;样条函数 - 馒头and花卷 - 博客园 三次样条&#xff08;cubic spline&#xff09;插值 - 知乎 B-Spline(三)样条曲线的性质 - Fun With GeometryFun With Geometry 个人理解的也不是非常深&#xff0c;但是大概要知道的就是样条具…...

计算机组成原理(判断题)

计算机控制器是根据事先编好的程序&#xff0c;根据其指令来进行控制只会每一步骤的操作&#xff1b; 面向主存的双总线结构计算机系统&#xff0c;因在CPU与主存之间增加了一组存储器总线&#xff0c;由于通过存储器总线访存&#xff0c;提高了CPU的访存速度&#xff0c;也减轻…...

error: failed to push some refs to ... 就这篇,一定帮你解决

目录 一、问题产生原因 二、解决办法 三、如果还是出问题&#xff0c;怎么办&#xff1f;&#xff08;必杀&#xff09; 一、问题产生原因 当你直接在github上在线修改了代码&#xff0c;或者是直接向某个库中添加文件&#xff0c;但是没有对本地库同步&#xff0c;接着你想…...

DAMA数据管理知识体系指南之数据仓库和商务智能管理

第9章 数据仓库和商务智能管理 9.1简介 数据仓库&#xff08;Data Warehouse,DW)由两个主要部分构成&#xff1a;首先是一个整合的决策支持数据库&#xff0c;其次是用于收集、清洗、转换、存储来自于各种操作型数据源和外部数据源数据的相关软件程序。两者结合以支持历史的、…...

PHP的五种常见设计模式

工厂模式 最初在设计模式 一书中&#xff0c;许多设计模式都鼓励使用松散耦合。要理解这个概念&#xff0c;让我们最好谈一下许多开发人员从事大型系统的艰苦历程。在更改一个代码片段时&#xff0c;就会发生问题&#xff0c;系统其他部分 —— 您曾认为完全不相关的部分中也有…...

教你搞懂线段树,从基础到提高

秋名山码民的主页 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f64f;作者水平有限&#xff0c;如发现错误&#xff0c;还请私信或者评论区留言&#xff01; 目录前言线段树逻辑概念线段树的俩个重要用处代码实现线段树题目巩固最后…...

C语言进阶——自定义类型:结构体

&#x1f307;个人主页&#xff1a;_麦麦_ &#x1f4da;今日名言&#xff1a;生活不可能像你想象的那么好&#xff0c;也不会像你想象的那么糟。——莫泊桑《羊脂球》 目录 一、前言 二、正文 1结构体 1.1结构体的基础知识 1.2结构的声明 1.3特殊的声明 1.4结构体变量的…...

SpringSecurity学习笔记01

目录 一、课程介绍 二、框架概述 三、入门案例 四、基本原理&#xff08;过滤器链&#xff09; 五、基本原理&#xff08;过滤器加载过程&#xff09; 六、基本原理&#xff08;两个重要的接口) 七、web权限方案-用户认证&#xff08;设置用户名密码上&#xff09; 八、…...

Python语言零基础入门教程(十一)

Python 列表(List) 序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置&#xff0c;或索引&#xff0c;第一个索引是0&#xff0c;第二个索引是1&#xff0c;依此类推。 Python有6个序列的内置类型&#xff0c;但最常见的是列表和元组。 序列都可以…...

现货白银基础知识

任何活动&#xff0c;任何项目&#xff0c;任何工作都离不开基础知识&#xff0c;这是肯定的。万丈高楼平地起&#xff0c;要想要简称百层高楼&#xff0c;首先得把低级打好&#xff01;现货白银投资也是一样的道理&#xff0c;现在我们就来一起聊聊现货白银基础知识的问题&…...

数据库原理及应用基础知识点

数据库原理基础知识点大全数据库原理及应用1、数据库系统概述1.1 基本概念1.2 数据模型1.3 数据库系统的结构2、实体 -- 联系模型2.1 基本概念2.2 实体-联系图2.3 弱实体集3、关系数据模型3.1 关系数据库的结构3.2 从ER模型到关系模型3.3 关系操作、完整性约束、关系代数4、关系…...

【数据结构】栈(stack)

写在前面本篇文章开始讲解栈的有关知识&#xff0c;其实把顺序表和链表学好&#xff0c;那么这一章便不在话下&#xff0c;栈实际上就是顺序表或链表的一些特殊情况。用顺序表实现的栈叫做顺序栈用链表实现的栈叫做链栈文章的内容分为几个部分&#xff0c;希望读者能快速了解文…...

初识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文档工作

编写技术文档&#xff0c;是令众多开发者望而生畏的任务之一。它本身是一件费时费力才能做好的工作。可是大多数时候&#xff0c;人们却总是想抄抄捷径&#xff0c;这样做的结果往往非常令人遗憾的&#xff0c;因为优质的技术文档是决定你的项目是否引人关注的重要因素。无论开…...

二级C语言操作例题(四十)

一、程序填空题 在此程序中&#xff0c;函数fun的功能是&#xff1a;在形参s所指字符串中寻找与参数c相同的字符&#xff0c;并在其后插入一个与之相同的字符&#xff0c;若找不到相同的字符则不做任何处理。 例如&#xff0c;若s所指字符串”baacda”&#xff0c;中c的字符为…...

vue-router 源码解析(二)-创建路由匹配对象

文章目录基本使用导语createRouterMatcher 创建匹配路由记录addRoute 递归添加matchercreateRouteRecordMatcher 创建matchertokenizePath 解析pathtokensToParser 记录打分insertMatcher 将matcher排序总结基本使用 const routes [{path:"/",component: Demo2,nam…...

分布式新闻项目实战 - 10.Long类型精度丢失问题

怒发冲冠&#xff0c;凭阑处、潇潇雨歇。抬望眼&#xff0c;仰天长啸&#xff0c;壮怀激烈。三十功名尘与土&#xff0c;八千里路云和月。莫等闲、白了少年头&#xff0c;空悲切。 靖康耻&#xff0c;犹未雪。臣子恨&#xff0c;何时灭。驾长车&#xff0c;踏破贺兰山缺。壮志饥…...

如何将本地jar包安装到maven仓库

mvn install:install-file:主要是将本地自定义jar安装到maven仓库&#xff0c;然后在pom中可以直接通过dependency的方式来引用。 此命令有如参数&#xff1a; 命令说明-DgroupId自定义groupId设置groupId 名-DartifactId自定义artifactId设置该包artifactId名-Dversion自定义…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...