二分查找法

   💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。



非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨
 

前言

本栏目将记录博主暑假从0开始刷力扣的算法题,每一条题目我都会把知识点抽丝剥茧地进行分析,以便大家更好的理解和学习,话不多说,肝!

序号标题力扣序号
1二分查找704
2搜索插入位置35
3x的平方根69
4有效的完全平方数367

1.二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

解题思路:

在升序数组 nums 中寻找目标值 target,对于特定下标 i,比较 nums[i] 和 target 的大小:

如果 nums[i]=target,则下标 i 即为要寻找的下标;

如果 nums[i]>target,则 target 只可能在下标 i 的左侧;

如果 nums[i]<target,则 target 只可能在下标 i 的右侧。

在二分查找中,使用 int mid = l + (r - l) / 2; 而不是 int mid = (l + r) / 2; 的主要原因是避免整数溢出。

代码(Java)

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] == target) {return mid;} else if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}return -1;}
}

二分查找法总结:

1.左闭右闭:

right = num.length - 1  假如数组为区间为【1,8】 那么right = 7  left = 0 

while(left <= right)  while循环里面的条件应该是   <=   因为假如区间是【1,1】 符合区间条件

mid > target    那么right = mid - 1  

mid < target    那么left = mid + 1

2.左闭右开

right = num.length -1  假如数组为区间为【1,8】 那么right = 8  left = 0  因为right = 8 取不到

while(left < right)  while循环里面的条件应该是   <   因为假如区间是【1,1) 符合区间条件

mid > target    那么 right =  mid

mid < target    那么  lef =  mid + 1


2.搜索插入位置

题目:

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

代码(Java):

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] == target){return mid;} else if(nums[mid] > target) {right = mid - 1;} else {left = mid + 1;}}return left;}
}

注意: 为什么最后返回left 

因为如果上面的没有返回return middle,说明最后一定是,left>right从而跳出循环的,在此之前是left=right,如果最后是right-1导致的left>right,说明原来的right位置是大于target的,所以返回原来的right位置即left位置;如果最后是left+1导致的left>right,说明是原来的的left=right这个位置小于target,而right能移动到这个位置,说明此位置右侧是大于target的,left现在加1就移动到了这样的位置,返回left即可

假设数组 nums = [1, 3, 5, 6],目标值 target = 2

  1. 初始化 left = 0 和 right = 3
  2. 进入循环,计算 mid = (0 + 3) / 2 = 1
  3. nums[mid] = 3,因为 3 > 2,所以更新 right = mid - 1 = 0
  4. 再次进入循环,计算 mid = (0 + 0) / 2 = 0
  5. nums[mid] = 1,因为 1 < 2,所以更新 left = mid + 1 = 1
  6. 此时,left 已经大于 right1 > 0),循环结束。

在循环结束时,left 指向了 2 应该被插入的位置,即在 1 和 3 之间,也就是索引 1 的位置。因此,返回 left(即 1)是正确的,它表示如果 target(在这个例子中是 2)被插入到数组中,它应该被放在索引 1 的位置。

假设数组 nums = [1, 3, 5, 7],目标值 target = 4

  1. 初始化 left = 0right = 3
  2. 计算 mid = (0 + 3) / 2 = 1(注意这里可能是整数除法,得到 1)。
  3. nums[mid] = 3,因为 3 < 4,所以更新 left = mid + 1 = 2
  4. 再次计算 mid = (2 + 3) / 2 = 2(或 2,取决于整数除法的行为)。
  5. nums[mid] = 5,因为 5 > 4,所以更新 right = mid - 1 = 1
  6. 此时,left 和 right 相等,但由于我们的循环条件是 left <= right,所以还会再执行一次循环(尽管这次循环可能不会改变任何东西,因为它会立即发现 nums[mid] 不等于 target,并且 left 和 right 已经相邻)。
  7. 在某次迭代中(在这个例子中可能不需要,但理论上可能发生),left 会增加,而 right 保持不变或者也减少,直到 left > right

3.x的平方根

题目:

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

代码(Java)

class Solution {public int mySqrt(int x) {int l = 0, r = x, ans = -1;while(l <= r) {int mid = l + (r - 1) / 2;if((long) mid * mid  <= x) {ans = mid;l = mid + 1;} else {r = mid - 1;}}return  ans;}
}


4.有效的完全平方数

题目:
 

给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数,如  sqrt 。

示例 1:

输入:num = 16
输出:true
解释:返回 true ,因为 4 * 4 = 16 且 4 是一个整数。

示例 2:

输入:num = 14
输出:false
解释:返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

代码(Java)

class Solution {public boolean isPerfectSquare(int num) {int left = 0, right = num;while(left <= right) {int mid = left + (right - left) / 2;long square = (long) mid * mid;if(square < num) {left = mid + 1;} else if (square > num) {right = mid -1;} else {return true;}}return false;}
}

❤️❤️❤️小郑是普通学生水平,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍

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

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

相关文章

SQL各种注入详解加案例--持续更新

sql注入 联合查询注入案例手工注入判断是否有SQL注入漏洞 sqlmap工具注入 报错注入常用的函数updatexml()函数案例 floor()涉及的函数实现手工注入sqlmap工具注入 盲注布尔盲注案例手工注入脚本sqlmap自动化工具 时间盲注 post注入GET传参和POST传参案例手工注入sqlmap工具 二次…

使用 Python 制作一个属于自己的 AI 搜索引擎

1. 使用到技术 OpenAI KEYSerper KEYBing Search 2. 原理解析 使用Google和Bing的搜搜结果交由OpenAI处理并给出回答。 3. 代码实现 import requests from lxml import etree import os from openai import OpenAI# 从环境变量中加载 API 密钥 os.environ["OPENAI_AP…

MySQL:索引(Index)语句

索引的限制 每个表最多可以有 16 个索引&#xff08;InnoDB 表的限制&#xff09;。 单个索引最多可以包含 16 列。 索引列的最大长度为 767 字节&#xff08;对于 CHAR, VARCHAR, 和 BINARY 类型&#xff09;&#xff0c;3072 字节&#xff08;对于 BLOB 类型&#xff09;。…

浅谈取样器插件之bzm - Free-Form Arrivals Thread Group

浅谈取样器插件之bzm - Free-Form Arrivals Thread Group bzm - Free-Form Arrivals (Ultimate Thread Group) 是一个高级且灵活的线程组插件&#xff0c;专为Apache JMeter设计。它扩展了JMeter的标准线程组功能&#xff0c;允许用户以自由形式定义线程&#xff08;用户&…

SSM项目学习:用xml配置文件或注解开发实现控制反转和依赖注入

什么是SSM SSMSpring(Spring Framework)Spring MVC mybatis Spring Framework系统架构 Spring Framework学习线路 IoC(Inversion of Control)和DI(Dependency Injection) 他们解决的问题&#xff1a;代码耦合度高的问题&#xff0c;需要类自己new对象&#xff0c;修改部分代…

03、DQL(数据查询语句)

目录 1、编写顺序 2、基本查询 3、条件查询 4、聚合函数 5、分组查询 6、排序查询 7、分页查询 8、执行顺序 1、编写顺序 SELECT 字段列表 FROM 表名列表 WHERE 条件列表 GROUP BY 分组字段列表 HAVING 分组后条件列表 ORDER BY 排序字段列表 LIMIT 分页参数2、基本查…

简单的docker学习 第11章 镜像中心

第11章 镜像中心 Docker Hub 与阿里云都是 Docker 的公网镜像中心&#xff0c;用户可以将自己的镜像 push 到公网镜像中心中自己的镜像仓库&#xff0c;并可将仓库设置为私有库&#xff0c;使他人无法看到&#xff0c;更无法 pull&#xff0c;以保证镜像的安全性。不过&#x…

【LeetCode刷题笔记】LCR.27 回文链表

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞 关注支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; 更多算法知识专栏&#xff1a;算法分析&#x1f525; 给大家跳段街舞感谢…

为什么康耐视visionpro的C#二次开发调用的recorddisplay控件偶尔会显示白色的,偶尔又正常了?

recorddisplay控件正常显示 异常显示 原因分析&#xff1a; 没有完全加载recorddisplay控件&#xff0c;有可能是有bug没有完全加载&#xff0c;打断点调试控件是否完全加载。

EMQX服务器安装MQTT测试

cd /usr/local/develop wget https://www.emqx.com/en/downloads/broker/5.7.1/emqx-5.7.1-el7-amd64.tar.gz mkdir -p emqx && tar -zxvf emqx-5.7.1-el7-amd64.tar.gz -C emqx ./emqx/bin/emqx start 重启 ./emqx/bin/emqx restart http://10.8.0.1:18083/ 账号ad…

【Kubernetes】应用的部署(一):金丝雀部署

应用的部署&#xff08;一&#xff09;&#xff1a;金丝雀部署 在项目迭代开发过程中&#xff0c;经常需要对应用进行上线部署。上线部署策略主要有 3 种&#xff1a;金丝雀部署、蓝绿部署 和 滚动部署。 金丝雀部署 也被叫作 灰度部署。金丝雀部署过程&#xff1a;先让一部分…

letcode 分类练习 哈希表 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

letcode 分类练习 哈希表 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和 242.有效的字母异位词349.两个数组的交集202.快乐数1.两数之和 242.有效的字母异位词 分别定义两个字母哈希表就可以了 class Solution { public:bool isAnagram(string s, strin…

搭建pxe网络安装环境

实验目的&#xff1a; 搭建pxe网络安装环境实现服务器自动部署 实验原理&#xff1a; PXE 网络安装环境实现服务器自动部署的实验原理为&#xff1a; 待安装的服务器&#xff08;PXE 客户端&#xff09;开机时&#xff0c;BIOS 设置从网络启动&#xff0c;向网络发送请求。…

科普文:JUC系列之ForkJoinPool源码解读ForkJoinWorkerThread

科普文&#xff1a;JUC系列之ForkJoinPool基本使用及原理解读-CSDN博客 科普文&#xff1a;JUC系列之ForkJoinPool源码解读概叙-CSDN博客 科普文&#xff1a;JUC系列之ForkJoinPool源码解读WorkQueue-CSDN博客 科普文&#xff1a;JUC系列之ForkJoinPool源码解读ForkJoinTask…

【第13章】Spring Cloud之Gateway全局异常处理

文章目录 前言一、异常处理1. 响应实体类2. 异常处理类 二、单元测试1. 无可用路由2. 服务不可用 总结 前言 网关作为我们对外服务的入口起着至关重要的作用&#xff0c;我们必须保证网关服务的稳定性&#xff0c;下面来为网关服务增加异常处理机制。 一、异常处理 1. 响应实…

K个一组翻转链表(LeetCode)

题目 给你链表的头节点 &#xff0c;每 个节点一组进行翻转&#xff0c;请你返回修改后的链表。 是一个正整数&#xff0c;它的值小于或等于链表的长度。如果节点总数不是 的整数倍&#xff0c;那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值&…

UE GAS学习

【Unreal】虚幻GAS系统快速入门-CSDN博客 GameplayTags FGameplayTags是一种层级标签&#xff0c;如Parent.Child.GrandChild。 通过GameplayTagManager进行注册。替代了原来的Bool&#xff0c;或Enum的结构&#xff0c;可以在玩法设计中更高效地标记对象的行为或状态。 Gamep…

牛客周赛 Round 54 (A~E)

#牛客周赛 Round 54 &#xff08;A~E&#xff09; 前言&#xff1a; 以后会定时更新很多比赛的题解 希望借此让自己坚持赛后补题 要不然写完就结束 自己水平没有一点提高 本人很菜所以不会更新 太难的题 加油&#xff01;&#xff01;&#xff01;1. ​清楚姐姐的糖葫芦…

C语言之递归函数

文章目录 &#x1f34a;自我介绍&#x1f34a;递归函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以&#xff1a;点赞关注评论收藏&#xff08;一键四连&#xff09;哦~ &#x1f34a;自我介绍 Hello,大家好&#xff0c;我是小珑也要变强&#xff08;也是小珑&…

C#学习笔记12:SYN6288语音模块_Winform上位机控制软件

今日尝试使用C# Winform写一个上位机软件控制 SYN6288语音模块 这里不讲什么基本原理(或者讲的比较略简)&#xff0c;直接讲实现了就...... 文章提供测试代码讲解、测试效果图、整体测试工程下载 目录 控件的摆放&#xff1a; SYN6288介绍: 代码编程&#xff1a; 对16进制发送…