二分查找法总结

目录

  • 1、思路讲解(LC704)
  • 2、代码思路讲解(循环不变量)
    • (1) 左闭右闭
    • (2)左闭右开
    • (3)总结:左开右闭和左闭右开
    • (4)复杂度分析
  • 3. 习题分析
    • (1)LC35 搜索插入位置 easy (二分查找法变种问题)
      • 思路
      • 代码
    • (2)LC34 在排序数组中查找元素的第一个和最后一个位置 medium(有重复元素的情况)
      • 思路1:二分查找+线性遍历
      • 思路2:扩展二分查找

1、思路讲解(LC704)

LC704:给定一个长度为 n n n的数组 nums ,元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素,则返回-1。
在这里插入图片描述

暴力法思路: n u m s [ 0 ] nums[0] nums[0]开始遍历一遍,time complexity = O ( n ) O(n) O(n)
二分法思路:
☀️首先要保证原序列是排好顺序的

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2、代码思路讲解(循环不变量)

伪代码:

def func(nums , target) -> int:# 初始化首元素、尾元素left = 0right = len(nums) - 1 or len(nums)# 循环while 满足左指针在右指针的左边:# 理论上 Python 的数字可以无限大(取决于内存大小),无须考虑大数越界问题m = (i + j) // 2  # 计算中点索引 mif nums[m] < target:# 说明target在nums[m]的右侧移动leftelif nums[m] > target:# 说明target在nums[m]的左侧else:return m  # 找到目标元素,返回其索引return -1  # 未找到目标元素,返回 -1

这里面有几个很容易出错的点(会导致循环不收敛
):

  • while的循环条件是: l e f t < = r i g h t left<=right left<=right or l e f t < r i g h t left<right left<right
  • 当nums[mid]<target的时候,应该是 l e f t = m i d + 1 left = mid+1 left=mid+1 or l e f t = m i d left = mid left=mid
  • 当nums[mid]>target的时候,应该是 r i g h t = m i d − 1 right = mid - 1 right=mid1 or r i g h t = m i d right = mid right=mid
    这几个问题的答案是:你定义的区间是什么样子的?

(1) 左闭右闭

如果定义的区间是左闭右闭的情况: [ l e f t , r i g h t ] [left,right] [left,right]

  • while的循环条件是: l e f t < = r i g h t left<=right left<=right (⭐️最推荐的选择,so easy)
    • 因为当 l e f t = r i g h t left=right left=right 的时候, [ l e f t , r i g h t ] [left,right] [left,right]区间中仍然有一个元素,所以仍然是合法的
  • 当nums[mid]<target的时候,应该是 l e f t = m i d + 1 left = mid+1 left=mid+1
    • 因为当nums[mid]<target的时候,就证明了mid指向的值一定不是目标值,所以left不应该指向mid,而应该是mid+1
  • 当nums[mid]>target的时候,应该是 r i g h t = m i d − 1 right = mid - 1 right=mid1 or r i g h t = m i d right = mid right=mid
def binary_search(nums: list[int], target: int) -> int:"""二分查找(双闭区间)"""# 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素i, j = 0, len(nums) - 1# 循环,当搜索区间为空时跳出(当 i > j 时为空)while i <= j:# 理论上 Python 的数字可以无限大(取决于内存大小),无须考虑大数越界问题m = (i + j) // 2  # 计算中点索引 mif nums[m] < target:i = m + 1  # 此情况说明 target 在区间 [m+1, j] 中elif nums[m] > target:j = m - 1  # 此情况说明 target 在区间 [i, m-1] 中else:return m  # 找到目标元素,返回其索引return -1  # 未找到目标元素,返回 -1

(2)左闭右开

如果定义的区间是左闭右开的情况: [ l e f t , r i g h t ) [left,right) [left,right)

  • while的循环条件是: l e f t < r i g h t left<right left<right
    • 因为当 l e f t = r i g h t left=right left=right 的时候, [ l e f t = r i g h t , r i g h t ) [left=right,right) [left=right,right)区间就会既有right又没有right,这种情况显然是不合法的
  • 当nums[mid]<target的时候,应该是 l e f t = m i d + 1 left = mid+1 left=mid+1
    • 因为当nums[mid]<target的时候,就证明了mid指向的值一定不是目标值,所以left不应该指向mid,而应该是mid+1
  • 当nums[mid]>target的时候,应该是 r i g h t = m i d right = mid right=mid
    • 因为区间是 [ l e f t , r i g h t ) [left,right) [left,right),当mid的值不是目标值的时候,区间应该是mid值前面的序列,但是因为右区间是开区间,所以可以直接将right指向mid。
def binary_search_lcro(nums: list[int], target: int) -> int:"""二分查找(左闭右开区间)"""# 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1i, j = 0, len(nums)# 循环,当搜索区间为空时跳出(当 i = j 时为空)while i < j:m = (i + j) // 2  # 计算中点索引 mif nums[m] < target:i = m + 1  # 此情况说明 target 在区间 [m+1, j) 中elif nums[m] > target:j = m  # 此情况说明 target 在区间 [i, m) 中else:return m  # 找到目标元素,返回其索引return -1  # 未找到目标元素,返回 -1

(3)总结:左开右闭和左闭右开

在这里插入图片描述

(4)复杂度分析

时间复杂度: O ( l o g n ) O(logn) O(logn) 每次循环区间减少一半,因此循环次数是 O ( l o g n ) O(logn) O(logn)
空间复杂度: O ( 1 ) O(1) O(1)没用使用数组啥的

3. 习题分析

(1)LC35 搜索插入位置 easy (二分查找法变种问题)

LC35:给定一个长度为 n n n的数组 nums ,元素按从小到大的顺序排列且不重复。给一个元素target,想要插入到nums中,并保持有序性。如果数组中存在target,就将targat插入到左侧;如果不存在,将target插入到按顺序插入的位置,返回索引。
在这里插入图片描述

思路

⭐️思考:
Q1: 当数组中有target的时候,插入点的索引是否就是返回值?
回答: yep!当查找到原数组有target值时,新的target要放在老的target的左侧,也就是说新的target代替了老的target的位置,也就是插入点的索引就是新插入的target的索引
Q2: 当数组不存在target的时候,新插入点是哪个元素的索引?
在这里插入图片描述

代码

def binary_search_insertion_simple(nums: list[int], target: int) -> int:"""二分查找插入点(无重复元素)闭区间"""i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]while i <= j:m = (i + j) // 2  # 计算中点索引 mif nums[m] < target:i = m + 1  # target 在区间 [m+1, j] 中elif nums[m] > target:j = m - 1  # target 在区间 [i, m-1] 中else:return m  # 找到 target ,返回插入点 m# 未找到 target ,返回插入点 ireturn i

(2)LC34 在排序数组中查找元素的第一个和最后一个位置 medium(有重复元素的情况)

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
在这里插入图片描述

思路1:二分查找+线性遍历

1️⃣ 执行二分查找,得到任意一个 target 的索引
2️⃣从找到的这个索引开始,分别向左和向右遍历,找到start和end指针

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if nums is None or len(nums) == 0:return [-1,-1]# 先用二分查找法找到target# 双闭区间(有重复元素)left = 0right = len(nums) - 1flag = 0while left <= right:mid = left + (right - left) // 2if target > nums[mid]: # 应该删除前半部分的元素left = mid + 1elif target < nums[mid]: # 应该删除后半部分的元素right = mid - 1else: # 当找到其中一个目标值之后,分别向前和向后遍历,找到起始和终止位置flag = 1start = midend = midwhile start >= 0 and nums[start] == target:start -= 1while end <= len(nums)-1 and nums[end] == target:end += 1breakif flag == 1:return [start+1,end-1]else:return [-1,-1]

时间复杂度: O ( n ) O(n) O(n),数组中存在很多重复的 target 时,该方法效率很低。

思路2:扩展二分查找

1️⃣查找左边界

  • 查找到任意一个target
  • 左边界 s t a r t start start必定在 [ l e f t , m i d − 1 ] [left,mid-1] [left,mid1]中,所以可以将 r i g h t = m i d − 1 right=mid-1 right=mid1,缩小区间,重新搜索一个新的target,新的target必定在源target的左侧
  • 因为想要最左侧target的索引,所以和LC704是一样的,最后返回的是 s t a r t = m i d start=mid start=mid

2️⃣查找右边界

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if nums is None or len(nums) == 0:return [-1,-1]# 扩展二分查找法:查找target时候使用二分查找法,确定边界的时候仍然使用二分查找法# 先用二分查找法找到左边界# 双闭区间(有重复元素)left = 0right = len(nums) - 1start = -1while left <= right:mid = left + (right - left) // 2if target > nums[mid]: # 应该删除前半部分的元素left = mid + 1elif target < nums[mid]: # 应该删除后半部分的元素right = mid - 1else: # 当找到其中一个目标值之后# 左边界start应该在[left,mid]之间right = mid - 1start = mid# 再用二分查找法找到右边界left = 0right = len(nums) - 1end = -1while left <= right:mid = left + (right - left) // 2if target > nums[mid]: # 应该删除前半部分的元素left = mid + 1elif target < nums[mid]: # 应该删除后半部分的元素right = mid - 1else: # 当找到其中一个目标值之后# 右边界end应该在[mid,right]之间left = mid + 1end = mid     return [start,end]   

时间复杂度: O ( l o g N ) O(logN) O(logN)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284563.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

老阳分享|temu跨境电商选品师项目能赚钱吗?

近年来&#xff0c;跨境电商行业蓬勃发展&#xff0c;成为众多创业者追逐的热点。其中&#xff0c;老阳分享的temu跨境电商选品师项目备受关注。那么&#xff0c;这个项目真的能赚钱吗?下面&#xff0c;我们就跟随本文去了解一下。 首先&#xff0c;temu作为拼多多旗下的跨境电…

数据结构与算法4-冒泡排序

文章目录 1. 认识冒泡排序2. 图示2.1 图示12.2 图示2 3. 代码 1. 认识冒泡排序 双层for循环&#xff0c;每次选出最大的数“浮”到数组的最后面&#xff1b;时间复杂度O( n 2 n^2 n2)&#xff0c;空间复杂度O(1);重复地遍历待排序的数列&#xff0c;一次比较两个元素&#xff…

ClickHouse部署安装

准备工作 确定防火墙处于关闭状态 CentOS取消打开文件数限制 在hadoop102的 /etc/security/limits.conf文件的末尾加入以下内容 注意&#xff1a;以下操作会修改 Linux 系统配置&#xff0c;如果操作不当可能导致虚拟机无法启动&#xff0c;建议在执行以下操作之前给…

Vue中的状态管理Vuex,基本使用

1.什么是Vuex? Vuex是专门为Vue.js设计的状态管理模式;特点:集中式存储和管理应用程序中所有组件状态,保证状态以一种可预测的方式发生变化。 1.1.什么是状态管理模式? 先看一个单向数据流的简单示意图 state:驱动应用的数据源 view:以声明方式将state映射到视图 actions:…

2024智能EDM邮件营销系统使用攻略

在数字化营销领域&#xff0c;智能EDM&#xff08;Electronic Direct Mail&#xff09;邮件营销作为一种高效、精准的推广方式&#xff0c;正日益受到企业的高度重视。而要实现这一策略的成功落地&#xff0c;一个高可靠性和高稳定性的专业邮件发送平台则是不可或缺的关键环节。…

arduino ide 开发esp8266注意事项

1.引脚序列号必须是常量来定义&#xff0c;否则会无限重启。 #define p2 2 const int Pin2p2; pinMode(Pin2, OUTPUT); 2.关于wifi的模式&#xff0c;ap,sta&#xff0c;apsta三种模式的初始化必须放在void set_up(){}这个函数里&#xff0c;不能额外搞个自定义函数&#xf…

SpringCloud-Gateway服务网关

一、网关介绍 1. 为什么需要网关 Gateway网关是我们服务的守门神&#xff0c;所有微服务的统一入口。 网关的核心功能特性&#xff1a; 请求路由 权限控制 限流 架构图&#xff1a; 权限控制&#xff1a;网关作为微服务入口&#xff0c;需要校验用户是是否有请求资格&am…

Python环境下基于1D-CNN的轴承故障诊断及TSNE特征可视化

1D CNN 处理一维信号具有显著优势&#xff0c;已在很多领域得到初步应用&#xff1a; 心电图监测&#xff1a;将1DCNN应用于心脏病监测&#xff0c;其方法是针对每一个心脏病人的&#xff0c;即对于每个心律失常患者使用该患者特有的训练数据&#xff0c;专门训练出一个紧凑的…

网络层(IP层)

IP协议的本质&#xff1a;有将数据跨网络传输的能力 而用户需要的是将数据从主机A到主机B可靠地跨网络传输 IP的组成&#xff1a;目标网络目标主机 IP由目标网络和目标主机两部分组成&#xff0c;IP报文要进行传输&#xff0c;要先到达目标网络&#xff0c;然后经过路由器转到…

保研复习概率论1

1.什么是随机试验&#xff08;random trial&#xff09;&#xff1f; 如果一个试验满足试验可以在相同的条件下重复进行、试验所有可能结果明确可知&#xff08;或者是可知这个范围&#xff09;、每一次试验前会出现哪个结果事先并不确定&#xff0c;那么试验称为随机试验。 …

利用 Claude 3 on Amazon Bedrock 和 Streamlit 的“终极组合”,开发智能对话体验

概述 通过本文&#xff0c;您将学会如何利用 Streamlit 框架快速搭建前端交互界面。该界面将集成图像上传功能&#xff0c;让用户可以方便地提交待处理图片。在后端&#xff0c;我们将借助 Amazon Bedrock 的 Message API&#xff0c;调用 Claude 3 家族中的 Sonnet 模型对图像…

代码随想录算法训练营Day55 ||leetCode 583. 两个字符串的删除操作 || 72. 编辑距离

583. 两个字符串的删除操作 这道题的状态方程比上一题简单一些 初始化如下 class Solution { public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size() 1, vector<int>(word2.size() 1));for (int i 0; i < word1…

Kafka生产者相关概念

文章目录 Kafka工作流程Kafka文件存储生产者分区策略生产者ISR生产者ack机制数据一致性问题ExactlyOnce Kafka工作流程 Kafka中消息是以topic进行分类的&#xff0c;Producer生产消息&#xff0c;Consumer消费消息&#xff0c;都是面向topic的。 Topic是逻辑上的概念&#xff…

Qt 压缩/解压文件

前面讲了很多Qt的文件操作&#xff0c;文件操作自然就包括压缩与解压缩文件了&#xff0c;正好最近项目里要用到压缩以及解压缩文件&#xff0c;所以就研究了一下Qt如何压缩与解压缩文件。 QZipReader/QZipWriter QZipReader 和 QZipWriter 类提供了用于读取和写入 ZIP 格式文…

SpringCloud Gateway工作流程

Spring Cloud Gateway的工作流程 具体的流程&#xff1a; 用户发送请求到网关 请求断言&#xff0c;用户请求到达网关后&#xff0c;由Gateway Handler Mapping&#xff08;网关处理器映射&#xff09;进行Predicates&#xff08;断言&#xff09;&#xff0c;看一下哪一个符合…

2024年C语言最新经典面试题汇总(11-20)

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…

深度学习 线性神经网络(线性回归 从零开始实现)

介绍&#xff1a; 在线性神经网络中&#xff0c;线性回归是一种常见的任务&#xff0c;用于预测一个连续的数值输出。其目标是根据输入特征来拟合一个线性函数&#xff0c;使得预测值与真实值之间的误差最小化。 线性回归的数学表达式为&#xff1a; y w1x1 w2x2 ... wnxn …

LeetCode每日一题——统计桌面上的不同数字

统计桌面上的不同数字OJ链接&#xff1a;2549. 统计桌面上的不同数字 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 思路&#xff1a; 这是一个很简单的数学问题&#xff1a; 当n 5时&#xff0c;因为n % 4 1&#xff0c;所以下一天4一定会被放上桌面 当n 4…

TnT-LLM: Text Mining at Scale with Large Language Models

TnT-LLM: Text Mining at Scale with Large Language Models 相关链接&#xff1a;arxiv 关键字&#xff1a;Large Language Models (LLMs)、Text Mining、Label Taxonomy、Text Classification、Prompt-based Interface 摘要 文本挖掘是将非结构化文本转换为结构化和有意义的…