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

Leetcode算法入门与数组丨5. 数组二分查找

文章目录

    • 1 二分查找算法
    • 2 二分查找细节
    • 3 二分查找两种思路
      • 3.1 直接法
      • 3.2 排除法

1 二分查找算法

二分查找算法是一种常用的查找算法,也被称为折半查找算法。它适用于有序数组的查找,并通过将待查找区间不断缩小一半的方式来快速定位目标值。

算法思想如下:

  1. 首先,确定待查找数组的起始位置(通常为数组的第一个元素)和结束位置(通常为数组的最后一个元素)。
  2. 然后,计算待查找区间的中间位置,即将起始位置和结束位置相加除以2。
  3. 比较中间位置的元素与目标值的大小关系:
  • 如果中间位置的元素等于目标值,则查找成功,返回中间位置。
  • 如果中间位置的元素大于目标值,则目标值可能在左半部分,将结束位置更新为中间位置的前一个位置。
  • 如果中间位置的元素小于目标值,则目标值可能在右半部分,将起始位置更新为中间位置的后一个位置。
  1. 重复步骤2和步骤3,直到找到目标值或者待查找区间为空(起始位置大于结束位置)为止。

二分查找算法的时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn) ,其中 n n n 为数组的大小。由于每次查找都将待查找区间缩小一半,因此它比线性查找算法更加高效。

2 二分查找细节

区间开闭问题

  • 左闭右闭区间:注意初始化时, r i g h t = l e n ( n u m s ) − 1 right = len(nums)-1 right=len(nums)1,数组最后一个元素位置。
  • 左闭右开区间:注意初始化时, r i g h t = l e n ( n u m s ) right = len(nums) right=len(nums),数组最后一个元素的下一个位置。
  • 一般情况,全部使用「左闭右闭区间」这种写法

m i d mid mid 取值问题

常见的两种取值公式

mid = (left + right) // 2   # 使用较多
mid = (left + right + 1) // 2
  • 当待查找区间中的元素个数为奇数个,使用这两种取值公式都能取到中间元素的下标位置。
  • 当待查找区间中的元素个数为偶数个
    • mid = (left + right) // 2 能取到中间靠左边元素的下标位置。
    • mid = (left + right + 1) // 2 能取到中间靠右边元素的下标位置。

出界条件的判断

两种判断方式

left <= right
left < right
  • left <= right,并且查找的元素不在有序数组中,则 while 语句的出界条件是 left > right,也就是 left == right + 1,写成区间形式就是 [ r i g h t + 1 right+1 right+1, r i g h t right right],此时待查找区间为空,待查找区间中没有元素存在,此时终止循环时,可以直接返回 −1。
  • left < right,并且查找的元素不在有序数组中,则 while 语句出界条件是 left == right,写成区间形式就是 [ r i g h t right right, r i g h t right right]。此时区间不为空,待查找区间还有一个元素存在,我们并不能确定查找的元素不在这个区间中,此时终止循环时,如果直接返回 −1 就是错误的。

使用 left < right 的话,可以在出界之后增加一层判断,判断是否等于目标元素。

# ...while left < right:# ...return left if nums[left] == target else -1

此时,在跳出循环的时候,一定是 left == right,无需判断此时应该返回 left or right

搜索区间范围的选择

三种写法

left = mid + 1,right = mid - 1
left = mid + 1 ,right = mid
left = mid,right = mid - 1

具体哪一种写法和二分查找的两种思路有关。

  • 思路 1:「直接法」—— 在循环体中找到元素后直接返回结果。
  • 思路 2:「排除法」—— 在循环体中排除目标元素一定不存在区间。

3 二分查找两种思路

3.1 直接法

  1. 设定左右边界为数组两端,即 l e f t = 0 , r i g h t = l e n ( n u m s ) − 1 left=0,right=len(nums)−1 left=0right=len(nums)1,代表待查找区间为 [ l e f t , r i g h t ] [left,right] [left,right](左闭右闭区间)。
  2. 取两个节点中心位置 m i d mid mid ,先比较中心位置值 n u m s [ m i d ] nums[mid] nums[mid] 与目标值 t a r g e t target target 的大小。
    1. 如果 t a r g e t = = n u m s [ m i d ] target==nums[mid] target==nums[mid],则返回中心位置。
    2. 如果 t a r g e t > n u m s [ m i d ] target>nums[mid] target>nums[mid] ,则将左节点设置为 m i d + 1 mid+1 mid+1,然后继续在右区间 [ m i d + 1 , r i g h t ] [mid+1,right] [mid+1,right] 搜索。
    3. 如果 t a r g e t < n u m s [ m i d ] target<nums[mid] target<nums[mid],则将右节点设置为 m i d − 1 mid−1 mid1,然后继续在左区间 [ l e f t , m i d − 1 ] [left,mid−1] [left,mid1] 搜索。
  3. 如果左边界大于右边界,查找范围缩小为空,说明目标元素不存在,此时返回 −1。
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1# 在区间 [left, right] 内查找 targetwhile left <= right:# 取区间中间节点mid = left + (right - left) // 2# 如果找到目标值,则直接范围中心位置if nums[mid] == target:return mid# 如果 nums[mid] 小于目标值,则在 [mid + 1, right] 中继续搜索elif nums[mid] < target:left = mid + 1# 如果 nums[mid] 大于目标值,则在 [left, mid - 1] 中继续搜索else:right = mid - 1# 未搜索到元素,返回 -1return -1

3.2 排除法

  1. 设定左右边界为数组两端,即 l e f t = 0 , r i g h t = l e n ( n u m s ) − 1 left=0,right=len(nums)−1 left=0right=len(nums)1,代表待查找区间为 [ l e f t , r i g h t ] [left,right] [left,right](左闭右闭区间)。
  2. 取两个节点中心位置 m i d mid mid ,比较中心位置值 n u m s [ m i d ] nums[mid] nums[mid] 与目标值 t a r g e t target target 的大小,先将目标元素一定不存在的区间排除。
  3. 然后在剩余区间继续查找元素,继续根据条件排除目标元素一定不存在的区间。
  4. 直到区间中只剩下最后一个元素,然后再判断这个元素是否是目标元素。
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1# 在区间 [left, right] 内查找 targetwhile left < right:# 取区间中间节点mid = left + (right - left) // 2# nums[mid] 小于目标值,排除掉不可能区间 [left, mid],在 [mid + 1, right] 中继续搜索if nums[mid] < target:left = mid + 1 # nums[mid] 大于等于目标值,目标元素可能在 [left, mid] 中,在 [left, mid] 中继续搜索else:right = mid# 判断区间剩余元素是否为目标元素,不是则返回 -1return left if nums[left] == target else -1
  • 直接法:更适合解决简单题目,数组中是非重复元素。
  • 排除法:更适合解决复杂题目,数组里可能不存在的元素,找边界问题。

参考文献

  • [1] https://datawhalechina.github.io/leetcode-notes/#/

—— END ——


如果以上内容有任何错误或者不准确的地方,欢迎在下面 👇 留言。或者你有更好的想法,欢迎一起交流学习~~~

更多精彩内容请前往 AXYZdong的博客

相关文章:

Leetcode算法入门与数组丨5. 数组二分查找

文章目录 1 二分查找算法2 二分查找细节3 二分查找两种思路3.1 直接法3.2 排除法 1 二分查找算法 二分查找算法是一种常用的查找算法&#xff0c;也被称为折半查找算法。它适用于有序数组的查找&#xff0c;并通过将待查找区间不断缩小一半的方式来快速定位目标值。 算法思想…...

拓扑关系如何管理?

在设备对接涂鸦的云端过程中&#xff0c;一部分设备由于自身资源或硬件配置&#xff0c;无法直接连接云端。而是需要通过网关进行中转&#xff0c;由网关代理实现和云端进行数据交互&#xff0c;间接实现设备接入云端。这样的设备也称为子设备。 要想实现网关代理子设备接入云…...

vue的由来、vue教程和M-V-VM架构思想、vue的使用、nodejs

vue vue的由来 vue教程和M-V-VM架构思想 vue的初步简单使用 nodejs vue的由来 # 1 HTML(5)、CSS(3)、JavaScript(ES5、ES6、ES11)&#xff1a;编写一个个的页面 -> 给后端(PHP、Python、Go、Java) -> 后端嵌入模板语法 -> 后端渲染完数据 -> 返回数据给前端 ->…...

课程表 循环依赖 拓扑排序 go语言

学会拓扑排序题目的基本解法 res数组 记录上课顺序g 记录学了课程i 能解锁的课程jindeg 记录每个课程的入度q 记录入度为0的课程 for循环q去解放其他课程 本题来自力扣课程表 func findOrder(numCourses int, prerequisites [][]int) []int {res : []int{}//建一个二维数组记…...

【红包雨接口设计】

一、服务器地址 http://rb.atguigu.cn 二、公共请求头参数 参数名称类型是否必选描述tokenString是用户唯一标识 备注&#xff1a;为了方便我们今天演示&#xff0c;服务端接受所有token。 三、接口 1. 创建红包雨 请求方式&#xff1a;GET请求地址&#xff1a;/api/v1/se…...

SSL证书到期更换证书会影响排名吗?

在现代的数字化时代&#xff0c;网络安全和用户体验成为了网站运营商和开发者们需要高度关注的问题。SSL证书作为一种重要的安全协议&#xff0c;对网站的安全性和用户信任起着至关重要的作用。然而&#xff0c;随着SSL证书的有效期限届满&#xff0c;许多网站运营商面临着更换…...

前端常用库之-JavaScript工具库lodash

文章目录 前端常用库之-JavaScript工具库lodash一、什么是lodash二、安装三、lodash使用Lodash 的 pick() 函数介绍和使用react 实例demo&#xff1a;pick结合...展开运算符(spread operator) 前端常用库之-JavaScript工具库lodash 一、什么是lodash 官网&#xff1a; https:…...

Linux- execve()

execve() 是 Linux/UNIX 中的 exec 函数家族中的一个&#xff0c;它允许进程执行一个新的程序。具体地&#xff0c;execve() 替换当前进程的映像为新的程序映像。 函数原型如下&#xff1a; int execve(const char *pathname, char *const argv[], char *const envp[]);pathn…...

007 数据结构_堆——“C”

前言 本文将会向您介绍关于堆Heap的实现 具体步骤 tips&#xff1a;本文具体步骤的顺序并不是源代码的顺序 typedef int HPDataType; typedef struct Heap {HPDataType* _a;int _size;int _capacity; }Heap;初始化 void HeapCreate(Heap* hp, HPDataType* a, int n) {hp-&…...

zabbix的原理与安装

一、Zabbix介绍 1、zabbix 是什么&#xff1f; zabbix是一个开源的IT基础监控软件&#xff0c;能实时监控网络服务&#xff0c;服务器和网络设备的状态&#xff0c;如网络使用&#xff0c;CPU负载、磁盘空间等&#xff0c;主要是包括数据的收集、报警和通知的可视化界面zabbi…...

ReactNative中升级IOS 17版本Crash解决

ReactNative中升级IOS 17版本Crash解决 ReactNative中升级IOS 17版本Crash解决一、问题描述二、原因分析三、解决方案决策3.1 设置宽高为非零值3.2 使用新的UIGraphicsImageRenderer替换就版本的UIGraphicsBeginImageContext 四、可能使用到该API的三方库4.1 react-native-fast…...

MongoDB详解

一、MongoDB概述 MongoDB 是一个基于 分布式文件存储 的开源 NoSQL 数据库系统&#xff0c;由 C 编写的。MongoDB 提供了 面向文档 的存储方式&#xff0c;操作起来比较简单和容易&#xff0c;支持“无模式”的数据建模&#xff0c;可以存储比较复杂的数据类型&#xff0c;是一…...

【SpringCloud微服务全家桶学习笔记-服务注册zookeeper/consul】

SpringCloud微服务全家桶学习笔记 Eureka服务注册 gitee码云仓库 9.其他服务注册框架 &#xff08;1&#xff09;zookeeper安装与使用 zookeeper需安装在虚拟机上&#xff0c;建议使用CentOS&#xff0c;安装地址如下&#xff1a; zookeeper镜像源 选择第一个进入后下载ta…...

【滑动窗口】LCR 016. 无重复字符的最长子串

LCR 016. 无重复字符的最长子串 解题思路 窗口内的字符串就是不重复子串每次遇到新的字符 看看窗口内是否存在该字符 如果存在直接剔除 然后调整窗口左边界不存在 添加窗口内部 右边界 class Solution {public int lengthOfLongestSubstring(String s) {if(s.length() < …...

C++中将类成员函数作为变量传递给函数

假设类ClassName有一个成员函数 void ClassName::funcname(int);通过typedef定义一个类成员函数指针类型,参数和返回值类型都要与成员函数对应 typedef void (ClassName::*FuncPtr)(int); // 定义类成员函数指针获取到的参数就是 FuncPtr pf...

2024届数字IC设计秋招面经-鼎信

背景 985硕士&#xff0c;计算机科班&#xff0c;实验室做cpu设计和fpga算法加速&#xff0c;我做处理器安全方向&#xff0c;有项目。 投递 8.25 没有笔试&#xff0c;两轮面试&#xff0c;直接通知下周一面试&#xff0c;草草的准备了下。 一面 技术面 9.4 不到半小时 …...

【数据结构】二叉树的节点数,叶子数,第K层节点数,高度,查找x节点,判断是否为完全二叉树等方法

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

前馈神经网络(FFNN)和多层感知机(MLP)

多层感知器&#xff08;MLP, Multi-Layer Perceptron&#xff09;和前馈神经网络&#xff08;Feed-Forward Neural Network, FFNN&#xff09;是深度学习中两个经常被使用的术语&#xff0c;它们经常被互换使用。让我们详细地了解这两个术语&#xff1a; 多层感知器 (MLP): M…...

EasySwipeMenuLayout - 独立的侧滑删除

官网 GitHub - anzaizai/EasySwipeMenuLayout: A sliding menu library not just for recyclerview, but all views. 项目介绍 A sliding menu library not just for recyclerview, but all views. Recommended in conjunction with BaseRecyclerViewAdapterHelper Feature…...

优麒麟下载、安装、体验

下载 官网 优麒麟 点击增强版、或者基础版进行下载 虚拟机安装 选择镜像 修改名称和存储路径 设置为50G 下一步&#xff0c;点击完成 开启安装 设置语言 去掉下载更新选项 继续 点击restart now 输入密码 出现下图说明安装成功&#xff0c;可以畅快的使用了...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...