刷题之Leetcode704题(超级详细)
704. 二分查找
力扣题目链接(opens new window)
https://leetcode.cn/problems/binary-search/
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间。
思路
这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。
二分查找涉及的很多的边界条件,逻辑比较简单,但就是写不好。例如到底是 while(left < right) 还是 while(left <= right),到底是right = middle呢,还是要right = middle - 1呢?
大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。
下面我用这两种区间的定义分别讲解两种不同的二分写法。
二分法第一种写法
第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] (这个很重要非常重要)。
区间的定义这就决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下两点:
- while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1
代码如下:(详细注释)
class Solution {public int search(int[] nums, int target) {// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target < nums[0] || target > nums[nums.length - 1]) {return -1;}int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid - 1;}return -1;}
}
- 时间复杂度:O(log n)
- 空间复杂度:O(1)
二分法第二种写法
如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。
有如下两点:
- while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
- if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]
代码如下:(详细注释)
class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid;}return -1;}
}
- 时间复杂度:O(log n)
- 空间复杂度:O(1)
总结
二分法是非常重要的基础算法,为什么很多同学对于二分法都是一看就会,一写就废?
其实主要就是对区间的定义没有理解清楚,在循环中没有始终坚持根据查找区间的定义来做边界处理。
区间的定义就是不变量,那么在循环中坚持根据查找区间的定义来做边界处理,就是循环不变量规则。
本篇根据两种常见的区间定义,给出了两种二分法的写法,每一个边界为什么这么处理,都根据区间的定义做了详细介绍。
相信看完本篇应该对二分法有更深刻的理解了。
相关题目推荐
. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/search-insert-position/description/
- . - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/ - 69.x 的平方根(opens new window)
https://leetcode.cn/problems/sqrtx/ - 367.有效的完全平方数(opens new window)
https://leetcode.cn/problems/valid-perfect-square/
相关文章:
刷题之Leetcode704题(超级详细)
704. 二分查找 力扣题目链接(opens new window)https://leetcode.cn/problems/binary-search/ 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标&am…...
leetcode热题100.前k个高频元素
作者:晓宜 🌈🌈🌈 个人简介:互联网大厂Java准入职,阿里云专家博主,csdn后端优质创作者,算法爱好者 ❤️❤️❤️ 你的关注是我前进的动力😊 Problem: 347. 前 K 个高频元…...
LangChain Demo | Agent X ReAct X wikipedia 询问《三体》的主要内容
背景 LangChain学习中,尝试改了一下哈里森和吴恩达课程当中的问题,看看gpt-3.5-turbo在集成了ReAct和wikipedia后,如何回答《三体》的主要内容是什么这个问题,当然,主要是为了回答这问题时LangChain内部发生了什么。所…...
Revit 2025新功能一览~
Hello大家好!我是九哥~ Revit2025已经更新,安装后,简单试了下,还是挺不错的,流畅度啊,新功能啊,看来还是有听取用户意见的,接下来就简单看看都有哪些新功能。 好了,今天的…...
Head First Design Patterns -代理模式
什么是代理模式 代理模式为另一个对象提供替身或者占位符,以便控制客户对对象的访问,管理访问的方式有很多种。例如远程代理、虚拟代理、保护代理等。 远程代理:管理客户和远程对象之间的交互。 虚拟代理:控制访问实例化开销大的对…...
第十三题:天干地支
题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个,分别为:甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊(w)、己&a…...
8000预算可以购买阿里云服务器配置整理
一个月8000元预算如何选择阿里云服务器配置?八千预算可选的阿里云服务器配置相当高了,这个预算可以购买阿里云企业级独享型云服务器,至少8核以上的配置,这个预算可以支持复杂、高负载或大规模的业务需求。阿里云服务器网整理8000元…...
游戏APP如何提高广告变现收益的同时,保证用户留存率?
APP广告变现对接第三方聚合广告平台主要通过SDK文档对接,一些媒体APP不具备专业运营广告变现的对接能力和资源沉淀,导致APP被封控,设置列入黑名单,借助第三方聚合广告平台进行商业化变现是最佳选择。#APP广告变现# 接入第三方平台…...
Linux ulimit命令教程:如何查看和设置系统资源限制(附实例详解和注意事项)
Linux ulimit命令介绍 ulimit是一个内置的Linux shell命令,它允许查看或限制单个用户可以消耗的系统资源量。在有多个用户和系统性能问题的环境中,限制资源使用是非常有价值的。 Linux ulimit命令适用的Linux版本 ulimit命令在所有主流的Linux发行版中…...
(delphi11最新学习资料) Object Pascal 学习笔记---第8章第5节(封闭类和Final方法)
8.5.2 封闭类和Final方法 如前所述,Java 采用非常动态的方法,默认情况下采用延迟绑定(或虚函数)。因此,Java 语言引入了一些概念,如不能继承的类(封闭类)和不能在派生类中覆盖的方法…...
vue3从精通到入门12:vue3的生命周期和组件
生命周期: 生命周期钩子主要包括: beforeCreate:组件实例被创建之前调用。在这个阶段,组件的 props 和 data 还未被初始化。created:组件实例创建完成后调用。在这个阶段,组件的 props 和 data 已经被初始…...
力扣热题100_链表_21_合并两个有序链表
文章目录 题目链接解题思路解题代码 题目链接 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 [1,2,4], l2 [1,3,4] 输出:[1,1,2,3,4,4] 示例…...
探索未来智慧酒店网项目接口架构
在数字化时代,智慧酒店已成为酒店业发展的重要趋势之一。智慧酒店网项目接口架构作为支撑智慧酒店运营的核心技术之一,其设计和优化对于提升用户体验、提高管理效率具有重要意义。本文将深入探讨智慧酒店网项目接口架构的设计理念和关键要素。 ### 智慧…...
os模块篇(十三)
文章目录 os.mknod(path, mode0o600, device0, *, dir_fdNone)os.major(device, /)os.minor(device, /)os.makedev(major, minor, /)os.pathconf(path, name)os.readlink(path, *, dir_fdNone)os.remove(path, *, dir_fdNone)os.removedirs(name)os.rename(src, dst, *, src_di…...
【JavaEE初阶系列】——文件操作 IO 之 文件系统操作
目录 📝认识文件 🚩树型结构组织 和 目录 🎈绝对路径和相对路径 🚩文件类型 📝文件系统操作 🎈File 概述 🎈File类的使用 1. 绝对路径 vs 相对路径 2. 路径分隔符 3. 静态成员变量 4…...
JAVA 学习·类与方法
不同于 C ,Java 是一门面向对象的编程语言。C 也有面向对象的内容,但是 C 和 Java 在方法的具体实现上存在区别。 方法的定义 方法(method)是为执行一个复杂操作组合在一起的语句集合。一个类中可以声明多个方法。其语法是采用 BNF 范式(Bac…...
4. python练习题4-水仙花数
4. python练习题4-水仙花数 【目录】 文章目录 4. python练习题4-水仙花数1. 目标任务2. 水仙花数的特点3. 如何判断一个数是否是水仙花数?4. 打印3位水仙花数5. 判断一个数是不是水仙花数6. 列表推导式6. 列表推导式判断一个数是不是水仙花数 【正文】 1. 目标任务…...
【Qt 学习笔记】Qt 开发环境的搭建 | Qt 安装教程
博客主页:Duck Bro 博客主页系列专栏:Qt 专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞👍收藏⭐评论✍ Qt 开发环境的搭建 | Qt 安装教程 文章编号:Qt 学习笔记 /…...
ids工业相机与电控位移台同步控制及数据采集
通过VS2017和OpenCV,实现ids工业相机与电控位移台同步控制及数据采集 目录项目环境配置代码流程及思路项目架构项目开发运行效果开发关键ids相机配置位移台环境配置相机头文件相机参数设置保存图像函数设置电控位移台头文件电控位移台设置参数最后就是通过main函数进行调用和控…...
景联文科技提供高质量医疗健康AI大模型数据
医疗行业是典型的知识和技术密集型行业,其发展水平直接关系到国民健康和生命质量。 医疗健康AI大模型,作为人工智能的一个分支,能够通过学习大量的数据来生成新的数据实例,在医药研发、医学影像、医疗文本分析等都有广泛的应用前景…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
