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

Python二分查找【清晰易懂】

1. 二分查找是什么?

想象你在玩“猜数字”游戏:

  • 对方心里想一个 1~100 的数字,你每次猜一个数,对方会告诉你是“大了”还是“小了”。

  • 最快的方法:每次都猜中间的数!比如第一次猜50,如果大了,就猜25;如果小了,就猜75。

  • 这样每次都能排除一半的可能性,最多7次就能猜中(因为2^7=128>100)!

这就是二分查找的核心思想——每次砍掉一半的搜索范围


2. 二分查找的条件

  • 必须是有序的列表(比如从小到大排列的数字)。

  • 如果列表是乱序的,二分查找会失效。


3. 代码示例(Python)

def binary_search(arr, target):left, right = 0, len(arr) - 1  # 初始化搜索范围:整个列表while left <= right:mid = (left + right) // 2  # 取中间位置if arr[mid] == target:return mid  # 找到了,返回索引elif arr[mid] < target:left = mid + 1  # 目标在右半部分else:right = mid - 1  # 目标在左半部分return -1  # 没找到# 测试
nums = [1, 3, 5, 7, 9]
print(binary_search(nums, 5))  # 输出2(因为5的索引是2)
print(binary_search(nums, 4))  # 输出-1(4不在列表中)

4. 复杂二分查找题目示例

在旋转有序数组中搜索目标值

题目描述

假设一个按升序排列的数组在某个未知点进行了旋转(例如 [0,1,2,4,5,6,7] 旋转后可能变成 [4,5,6,7,0,1,2])。
给定一个目标值 target,如果它存在于旋转后的数组中,则返回其索引,否则返回 -1
要求时间复杂度为 O(log n)

示例 1

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4(0的索引是4)

示例 2

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1(3不存在)
解题思路

处理局部有序性

旋转有序数组由两个升序子数组组成(例如 [4,5,6,7,0,1,2] 分为 [4,5,6,7] 和 [0,1,2])。

  • 左半部分:所有元素 ≥ 第一个元素(如 4,5,6,7 ≥ 4)。

  • 右半部分:所有元素 < 第一个元素(如 0,1,2 < 4)。

需要区分左半部分还是右半部分是因为二分查找依赖有序性,只有确定 mid 在哪个部分,才能正确判断 target 可能的位置。

直观例子

以数组 [4,5,6,7,0,1,2] 和 target=0 为例:

  1. 初始状态:left=0right=6mid=3(值 7)。

    nums[3] >= nums[0]7 >= 4)→ mid 在左半部分。target=0 不在 [4,7) 范围内 → 调整 left=4
  2. 下一轮:left=4right=6mid=5(值 1)。

    nums[5] < nums[4]1 < 0 不成立)→ mid 在右半部分。target=0 不在 (1,2] 范围内 → 调整 right=4
  3. 找到目标:nums[4] == 0,返回索引 4

代码实现
def search(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return mid# 判断mid位于左半部分还是右半部分if nums[mid] >= nums[left]:  # mid在左半部分(较大的一半)if nums[left] <= target < nums[mid]:right = mid - 1  # target在左半部分的左侧else:left = mid + 1   # target在左半部分的右侧或右半部分else:  # mid在右半部分(较小的一半)if nums[mid] < target <= nums[right]:left = mid + 1    # target在右半部分的右侧else:right = mid - 1   # target在右半部分的左侧或左半部分return -1# 测试
nums = [4,5,6,7,0,1,2]
print(search(nums, 0))  # 输出4
print(search(nums, 3))  # 输出-1

相关文章:

Python二分查找【清晰易懂】

1. 二分查找是什么&#xff1f; 想象你在玩“猜数字”游戏&#xff1a; 对方心里想一个 1~100 的数字&#xff0c;你每次猜一个数&#xff0c;对方会告诉你是“大了”还是“小了”。 最快的方法&#xff1a;每次都猜中间的数&#xff01;比如第一次猜50&#xff0c;如果大了&…...

【数据分享】基于联合国城市化程度框架的全球城市边界数据集(免费获取/Shp格式)

在全球城市化进程不断加快的今天&#xff0c;如何精准定义和测量“城市”成为关键问题。不同国家和机构采用不同的标准&#xff0c;导致全球城市化水平的统计结果存在较大差异。同时&#xff0c;由于数据来源分散、标准不统一&#xff0c;获取一套完整、可比的全球城市边界数据…...

ExpTimerApcRoutine函数分析之作用是ActiveTimerListHead里面移除定时器_etimer

第一部分&#xff1a; VOID ExpTimerApcRoutine ( IN PKAPC Apc, IN PKNORMAL_ROUTINE *NormalRoutine, IN PVOID *NormalContext, IN PVOID *SystemArgument1, IN PVOID *SystemArgument2 ) /* Routine Description: This function is the special …...

Linux环境下安装部署Docker

windows下连接Linux&#xff1a; 打开终端&#xff1a; //ssh远程连接 ssh root192.168.xx.xx//输入账号密码 root192.168.xx.xxs password: ssh连接成功&#xff01; 安装Docker&#xff1a; //安装Docker yum install -y yum-utils device-mapper-persistent-data lvm2 …...

深度赋能!北京智和信通融合DeepSeek,解锁智能运维无限可能

在数字化飞速发展的今天&#xff0c;传统运维模式面临着设备规模激增、故障复杂度攀升、人工响应滞后等多重挑战。随着DeepSeek、腾讯元宝等AI大模型的兴起&#xff0c;为传统运维模式带来了新的变革。 北京智和信通基于DeepSeek大模型技术&#xff0c;将AI和运维场景深度融合&…...

mysql死锁排查解决

今天数据库突然报错[40001][1213] Deadlock found when trying to get lock; try restarting transaction 一看就是死锁 阿里实列会显示类似sql:UPDATE goods SET num num - 1 WHERE id2 AND num > 1; 一看sql这不是扣减库存操作吗&#xff1f; 为什么这sql会出现死锁??…...

Linux | i.MX6ULL 终结者学习指南(1)

01 一 光盘资料介绍 跟我一起成为嵌入式Linux大佬&#xff0c;开干 02 接下来我们一起学习。 01_开发及烧写工具 &#xff08;Linux 镜像烧写工具、交叉编译器、裸机镜像制作工具&#xff09; 1.交叉编译器 &#xff08;ARM 交叉编译器&#xff09; 2.裸机镜像制作…...

NX二次开发刻字功能——布尔运算

刻字功能在经历、创建文本、拉伸功能以后就剩下布尔运算了。布尔运算的目的就是实现文本时凸还是凹。这部分内容很简单。 1、首先识别布尔运算的类型&#xff0c;我这里用到一个枚举类型的选项&#xff0c;凸就是布尔求和&#xff0c;凹就是布尔求差。 2、其放置位置为创建拉伸…...

SpringAI与JBoltAI深度对比:从工具集到企业级AI开发范式的跃迁

一、Java生态下大模型开发的困境与需求 技术公司的能力断层 多数企业缺乏将Java与大模型结合的标准开发范式&#xff0c;停留在碎片化工具使用阶段。 大模型应用需要全生命周期管理能力&#xff0c;而不仅仅是API调用。 工具集的局限性 SpringAI作为工具集的定位&#xff1…...

JAVASCRIPT 异步函数:底层原理,fetch,promise实例方法then, catich

什么是异步 所谓“异步函数”通常指这样一种函数&#xff1a;它在编写时会调用异步 API 并在某个时机&#xff08;可能是定时、可能是等待网络、也可能是其他操作&#xff09;把结果“异步”地返回。而“回调函数”是异步函数执行完成后会去调用的函数&#xff0c;也就是“等待…...

docker run -p 5000:5000 my-flask-app

docker run -p 5000:5000 my-flask-app代码的意思是&#xff1a; 运行 my-flask-app 容器&#xff0c;并把 Flask 服务器的 5000 端口映射到本机的 5000 端口。 拆解解释 docker run -p 5000:5000 my-flask-app✅ docker run → 运行一个 Docker 容器 ✅ -p 5000:5000 → 端口…...

头文件“stm32f10x.h“与 “stdint.h“和“stdio.h“之间的关系

目录 一、#include "stm32f10x.h"包含#include "stdint"吗&#xff1f; 1、直接包含情况 2、间接依赖情况 3、实际使用建议 二、#include "stm32f10x.h"包含#include "stdio.h"吗&#xff1f; 1、头文件功能与设计目的差异 2、实…...

前端常问的宏观“大”问题详解

HTML5新特性包括那些 HTML5新特性详解 HTML5作为现代网页开发的核心标准,引入了多项革新特性,涵盖语义化标签、多媒体支持、表单增强及新API等,显著提升了网页功能与开发效率。以下是其核心新特性的分类总结: 一、语义化标签 HTML5新增了语义化布局标签,替代传统无意义…...

华为机试练习

挑7_牛客题霸_牛客网 整数转换为字符串String numStr String.valueOf(str); String有一个contains方法&#xff0c;查看是否包含字符串 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String…...

压力测试未覆盖边界条件的后果有哪些

压力测试未覆盖边界条件可能导致的主要后果包括产品稳定性下降、潜在故障隐患未被识别、用户体验下降及企业信誉受损。其中&#xff0c;最直接且明显的后果是产品稳定性下降。产品在极限或边界条件下通常最容易暴露缺陷&#xff0c;如果压力测试未充分覆盖这些边界条件&#xf…...

编程技术水平横向和垂直发展的抉择全方位分析

文章目录 摘要引言一、横向发展的全面分析二、垂直发展的深度剖析三、发展路径的决策模型四、两者结合的协同策略五、行业应用与趋势分析六、结论 摘要 本文全面分析了编程技术发展中横向扩展与垂直深化的战略抉择。通过系统比较两种发展路径的特点、优势、劣势及应用场景&…...

Docker技术系列文章,第十篇——Docker 集群与编排(以 Kubernetes 为例)

本篇内容作为docker系列的收尾之作&#xff0c;之所以选择本篇作为收尾之作&#xff0c;是因为小编觉得 这十篇内容已经满足基础的docker应用中的需求了&#xff1b;关注小编&#xff0c;小编后期还会不定时的更新docker相关的知识点。希望诸君共同努力&#xff0c;都能收获的愈…...

iPhone mini,永远再见了

世界属于多数派&#xff0c;尽管有极少数人对 iPhone mini 情有独钟&#xff0c;但因为销量惨淡&#xff0c;iPhone mini 还是逃不开停产的命运。 据 Counterpoint 的数据&#xff0c;iPhone 12/13 mini 两代机型&#xff0c;仅占同期 iPhone 销量的 5%。 因为是小屏手机&…...

第五周日志-重新学汇编(2)

机器语言 汇编语言(直接在硬件上工作——硬件系统结构&#xff09;&#xff1a; 1.机器语言 每一种微处理器硬件设计和内部结构不同&#xff08;决定了电信号不同&#xff0c;进而需要不同的机器指令&#xff09; #早期通过纸带机/卡片机输入计算机&#xff0c;进行运算 2…...

Qt正则表达式QRegularExpression

在 Qt 中&#xff0c;正则表达式是处理文本的强大工具&#xff0c;它能够帮助我们匹配、搜索和替换特定的字符串模式。自 Qt 5 起&#xff0c;QRegularExpression 类提供了对 ECMAScript 标准的正则表达式支持&#xff0c;这使得它在处理各种复杂的字符串任务时变得更加高效和灵…...

Java-servlet(十)使用过滤器,请求调度程序和Servlet线程(附带图谱表格更好对比理解)

Java-servlet&#xff08;十&#xff09;使用过滤器&#xff0c;请求调度程序和Servlet线程 前言一、Servlet 间通信&#xff08;了解即可&#xff09;二、Servlet 请求处理&#xff1a;getAttribute 和 getParameter 的区别与应用1.getAttribute 方法2.getParameter 方法 三、…...

【环路补偿】环路补偿的九种类型-mathcad计算书免费下载

环路补偿的九种类型-mathcad计算书免费下载 通过网盘分享的文件&#xff1a;环路补偿的9种类型.xmcd 链接: https://pan.baidu.com/s/1QIwsKsbv-WyyYgGc4P1eqg?pwd4sar 提取码: 4sar --来自百度网盘超级会员v3的分享...

【极速版 -- 大模型入门到进阶】LORA:大模型轻量级微调

文章目录 &#x1f30a; 有没有低成本的方法微调大模型&#xff1f;&#x1f30a; LoRA 的核心思想&#x1f30a; LoRA 的初始化和 r r r 的值设定&#x1f30a; LoRA 实战&#xff1a;LoraConfig参数详解 论文指路&#xff1a;LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE M…...

六十天前端强化训练之第三十二天之Babel 转译配置大师级深度讲解

欢迎来到编程星辰海的博客讲解 看完可以给一个免费的三连吗&#xff0c;谢谢大佬&#xff01; 目录 一、核心概念与知识体系详解 1. Babel 工作原理全景解析 二、完整配置方案&#xff08;带详细注释&#xff09; 1. 进阶版 .babelrc 配置 2. Webpack 集成配置&#xff08…...

nginx部署前端项目(linux、docker)

引言 在CentOS 7系统上使用docker安装nginx&#xff0c;使用nginx部署一个由Vue开发、打包的项目 docker安装nginx 这里不多赘述&#xff0c;直接上docker-compose.yml代码 nginx:container_name: nginximage: nginx:1.27.2ports:- "80:80"volumes:- /docker/ngin…...

支付页面安全与E-Skimming防护----浅谈PCI DSS v4.0.1要求6.4.3与11.6.1的实施

关键词&#xff1a;支付页面安全、E-Skimming、PCI DSS v4.0.1、第三方脚本、风险管理、持卡人数据、数据安全、第三方服务提供商、TPSP、内容安全、网页监控、恶意脚本攻击 本文为atsec和作者技术共享类文章&#xff0c;旨在共同探讨信息安全的相关话题。转载请注明&#xff…...

配置完nfs后vmware虚拟机下ubuntu/无法联网问题

背景&#xff1a;我在用imx6ull配置完nfs和tftp后&#xff0c;哪怕还原了设置也连不上网&#xff0c;网上的教程都没用&#xff0c;什么配置路由&#xff0c;配置ip&#xff0c;配置什么用户文件&#xff0c;都没用&#xff0c;最后试出来了一个方法&#xff0c;解决问题。 方法…...

【含文档+PPT+源码】基于大数据的交通流量预测系统

项目介绍 本课程演示的是一款基于大数据的交通流量预测系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 包含&#xff1a;项目源码、项目文档、数据库脚本、软件工具等所有资料 带你从零开始部署运行本套系统 该项目附带的源码…...

关于Qt的各类问题

目录 1、问题&#xff1a;Qt中文乱码 2、问题&#xff1a;启动时避免ComBox控件出现默认值 博客会不定期的更新各种Qt开发的Bug与解决方法,敬请关注! 1、问题&#xff1a;Qt中文乱码 问题描述&#xff1a;我在设置标题时出现了中文乱码 this->setWindowTitle("算法…...

Oracle19C的启动及停止

在 Oracle 19c 中&#xff0c;停止和启动数据库实例是常见的操作。以下是详细的步骤&#xff0c;涵盖单实例和 RAC 环境。 1. 停止 Oracle 19c 数据库实例 1.1 使用 SQL*Plus 停止数据库 连接到数据库实例&#xff1a; sqlplus / as sysdba 停止数据库&#xff1a; 正常关闭…...

端侧设备(如路由器、家庭网关、边缘计算盒子、工业网关等)的典型系统、硬件配置和内存大小

🏠 家用/工业级边缘设备硬件概览 类型常见设备示例CPU 架构内存范围操作系统类型家用路由器TP-Link、小米、华硕、OpenWrtARM Cortex-A7/A964MB~256MBOpenWrt / DD-WRT / Embedded Linux智能家庭网关华为、绿米、天猫精灵、Aqara HubARM Cortex-M/R128MB~512MBEmbedded Lin…...

tcp接发json字符串

因工作需要对接硬件设备,需要通过tcp协议接收发送字符串,而字符串里面全是json字符串,登陆用json对象发送,心跳也用json发送,设备检测到信号后自动推送的也是json字符串,只要登陆后心跳就要每过10秒发送一次,而信号的推送则是在登陆后的任意时间发生.每个json与json之间没有换行…...

string模拟实现-C++

一、目标 string函数是C中常用的库函数&#xff0c;在string中有许多操作函数&#xff0c;对于一些常用的操作函数&#xff0c;我们可以自己模拟实现一下。 实现的操作有&#xff1a; 迭代器 构造函数 拷贝构造函数 析构函数 赋值运算符重载 c_str() size() [ ]运算符重…...

uni-app AES 加密

uni-app 官网没有 加密 API 我们 可以 安装 crypto-js npm install crypto-js他会保存到项目中 node_modules import CryptoJS from ../node_modules/crypto-js //引用AES源码js const keyCode 012345678 //密钥 const ivCode 012345678 //偏移量const key CryptoJS.enc.Ut…...

【STM32】GPIO输入(按键)

目录 一、如何分辨GPIO输入使用什么电频二、输入抖动问题如何消抖三、示例代码 一、如何分辨GPIO输入使用什么电频 先看原理图 即可知道他的初始输入状态需要高电平 判断可知使用上拉输入 二、输入抖动问题如何消抖 电路图中, 按键输入有额外的电容电阻, 是为了消抖 消抖方…...

Manus AI 与多语言手写识别技术解析

Manus AI 与多语言手写识别技术解析 Manus AI 是一家专注于人工智能技术的公司&#xff0c;其多语言手写识别技术在多个领域展现了强大的应用潜力。本文将从技术原理、应用场景、优势与挑战等方面&#xff0c;深入解析 Manus AI 的多语言手写识别技术。 1. 技术原理 (1) 手写…...

每日总结3.28

蓝桥刷题 3227 找到最多的数 方法一&#xff1a;摩尔投票法 #include <bits/stdc.h> using namespace std; #define int long long signed main() { int n,m; cin>>n>>m; int a[m*n]; for(int i0;i<n*m;i) { cin>>a[i]; } int cand…...

NX二次开发刻字功能——预览功能

这个预览功能其实在NX软件中很常见,有利于建模者确定刻字的位置,这个功能早在唐康林老师的超级长方体教程中出现过。我只是学以致用。把该功能集成刻字中。 在勾选预览的同时,如果点击放大镜也就是显示预览结果,要刻字的对象透明度数值为70,同时预览结果文字会变成撤销,如…...

算法 | 2024最新算法:鳑鲏鱼优化算法原理,公式,应用,算法改进研究综述,matlab代码

2024最新鳑鲏鱼优化算法(BFO)研究综述 鳑鲏鱼优化算法(Bitterling Fish Optimization, BFO)是2024年提出的一种新型群智能优化算法,受鳑鲏鱼独特的繁殖行为启发,通过模拟其交配、产卵和竞争机制进行全局优化。该算法在多个领域展现出优越性能,尤其在解决复杂非线性问题中…...

WPF基础知识(续)

六、WPF 中的样式和模板 样式定义&#xff1a; 可以在 XAML 中定义样式来统一 UI 元素的外观和风格。样式可以定义在资源字典中&#xff0c;也可以直接在窗口或控件的Resources属性中定义。例如&#xff0c;定义一个按钮的样式&#xff1a; <Window.Resources><Sty…...

Go 语言 sync 包使用教程

Go 语言 sync 包使用教程 Go 语言的 sync 包提供了基本的同步原语&#xff0c;用于在并发编程中协调 goroutine 之间的操作。 1. 互斥锁 (Mutex) 互斥锁用于保护共享资源&#xff0c;确保同一时间只有一个 goroutine 可以访问。 特点&#xff1a; 最基本的同步原语&#x…...

MybatisPlus(SpringBoot版)学习第四讲:常用注解

目录 1.TableName 1.1 问题 1.2 通过TableName解决问题 1.3 通过全局配置解决问题 2.TableId 2.1 问题 2.2 通过TableId解决问题 2.3 TableId的value属性 2.4 TableId的type属性 2.5 雪花算法 1.背景 2.数据库分表 ①垂直分表 ②水平分表 1>主键自增 2>取…...

集成开发环境革新:IntelliJ IDEA与Cursor AI的智能演进

集成开发环境革新&#xff1a;IntelliJ IDEA 与 Cursor AI 的智能演进 集成开发环境&#xff08;IDE&#xff09; 是软件开发者必不可少的工具。一个优秀的 IDE 不仅能够帮助编写和调试代码&#xff0c;还能集成版本控制和代码优化等多种功能。如今&#xff0c;随着人工智能&a…...

Qt弹出新窗口并关闭(一个按钮)

参考&#xff1a;Qt基础 练习&#xff1a;弹出新窗口并关闭的两种实现方式&#xff08;两个按钮、一个按钮&#xff09;_qt打开一个窗口另一个关闭-CSDN博客 实现&#xff1a; 一个按钮&#xff0c;点击一次&#xff0c;按钮的名字从open window变为close window&#xff0c;…...

暴力搜索算法详解与TypeScript实战

# 暴力搜索算法详解与TypeScript实战## 什么是暴力搜索&#xff1f;暴力搜索&#xff08;Brute Force Search&#xff09;是算法领域最基础的解题方法之一&#xff0c;其核心思想是**系统性地枚举所有可能的候选解**&#xff0c;并验证每个候选解是否满足问题条件。这种方法不依…...

[识记]Mysql8 远程授权

今天在测试docker时&#xff0c;因更换为Mysql8&#xff0c;使用SQL方式实现远程授权&#xff0c;其方式方法同于Mysql&#xff0c;但语句稍有不同&#xff0c;仅供参考。 登录mysql mysql -u root -p 输入密码: [请依据交互输入你的mysql密码]切换数据库 use mysql;选择需要…...

5.1 WPF路由事件以及文本样式

一、路由事件 WPF中存在一种路由事件&#xff08;routed event&#xff09;&#xff0c;该事件将发送到包含该控件所在层次的所有控件&#xff0c;如果不希望继续向更高的方向传递&#xff0c;只要设置e.Handled true即可。 这种从本控件-->父控件->父的父控件的事件&am…...

做规控算法时用到的一些简单函数和功能(c++)(持续更新中)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、将偏航角转换为四元数二、RCLCPP_INFO_STREAM(rclcpp::get_logger("mission_planner"),"&#xff08;打印标志位&#xff09;"<<…...

android studio 运行flutter项目

在Android Studio中运行Flutter项目 简介 Flutter是一个流行的跨平台移动应用开发框架&#xff0c;而Android Studio是一种强大的集成开发环境&#xff0c;支持Flutter开发。本文将介绍如何在Android Studio中运行Flutter项目&#xff0c;让开发者能够更加方便地进行Flutter应…...

如何用 Postman 进行高效的 Mock 测试?

Postman 是一个强大的 API 开发和测试工具&#xff0c;它可以让你轻松地创建和发送各种 HTTP 请求&#xff0c;查看响应结果&#xff0c;并进行调试和优化。但是有时候&#xff0c;你可能还没有开发好后端服务&#xff0c;或者想要模拟不同的响应场景&#xff0c;这时候就可以使…...