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

【手撕数据结构】二分查找(好多细节)

🌈键盘敲烂,年薪30万🌈

目录

普通版本的二分查找:

right只负责控制边界(少了两次比较):

时间复杂度更稳定的版本:

BSLeftmost:

BSRightmost:


 

普通版本的二分查找:

  • 🏸细节1:循环判定条件是left <= right
  • ⭐细节2:mid = (left + right ) >>> 1 原因见代码注释

/**** 二分查找的实现 3个版本* 时间复杂度:O(longn)* 空间复杂度:O(1)** 细节1:循环判定条件是left <= right* 细节2:mid计算要用 >>> 因为left + right 可能越界*      例如:right = Integer.MAX_INT-1 left = 0;*      第一轮计算没问题 假设mid < target*      left = mid + 1; 这是后left+ right 就超出int的最大范围,变成负数*      原因很简单:java没有无符号数,最高位表示符号位,/ 运算是先将补码转原码 >>>位运算是直接再二进制上运算*/
public class Demo1 {public static void main(String[] args) {int[] nums = {1,4,6,8,15,76,145};int target = 145;int index1 = method1(nums, target);System.out.println(target + "索引为" + index1);System.out.println(target + "索引为" + index2);}private static int method1(int[] nums, int target) {int left = 0, right = nums.length-1;while(left <= right){//细节 用无符号右移运算符int mid = (left + right) >>> 1;if(nums[mid] > target){right = mid - 1;}else if (nums[mid] < target){left = mid + 1;}else{return mid;}}return -1;}
}

right只负责控制边界(少了两次比较):

  • 改动1:while条件是left < right
  • 改动2:right = nums.length
public class Demo1 {public static void main(String[] args) {int[] nums = {1,4,6,8,15,76,145};int target = 145;int index2 = method2(nums, target);System.out.println(target + "索引为" + index2);}
}private static int method2(int[] nums, int target) {int left = 0, right = nums.length; //right 只代表有边界,不参与比较while(left < right){int mid = (left + right) >>> 1;if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid;}else {return mid;}}return -1;}

时间复杂度更稳定的版本:

  • 细节:减少了if比较次数
public class Demo1 {public static void main(String[] args) {int[] nums = {1,4,6,8,15,76,145};int target = 145;int index3 = method3(nums, target);System.out.println(target + "索引为" + index3);}
}    private static int method3(int[] nums, int target) {//这个最牛逼//减少循环内的比较次数int left = 0, right = nums.length;while(1 < right - left){int mid = (left + right) >>> 1;if(nums[mid] > target){right = mid;}else{left = mid;}}if(nums[left] == target){return left;}return -1;}

BSLeftmost:

/**** 应用:求成绩排名  求前任*/
public class Leftmost {public static void main(String[] args) {int[] nums = {1,2,4,4,4,6,7};int target = 3;/**** params* return 找到了 - 返回靠左的下标*        没找到 - 返回>target的最靠左下标*/int ans = BSLeftmost(nums, target);System.out.println(ans);}private static int BSLeftmost(int[] nums, int target) {int left = 0, right = nums.length -1;while(left <= right){int mid = (left+right) >>> 1;if(target > nums[mid]){left = mid + 1;} else{right = mid - 1;}}return left;}
}

BSRightmost:

/**** 求后任*/
public class Rightmost {public static void main(String[] args) {int[] nums = {1,2,4,4,4,6,7};int target = 3;/*** return 找到了返回下标*        没找到返回 <= targer的最靠右索引**/int ans = BSRightmost(nums, target);System.out.println(ans);}private static int BSRightmost(int[] nums, int target) {int left = 0, right = nums.length-1;while(left <= right){int mid = (left + right) >>> 1;if(target >= nums[mid]){left = mid + 1;}else {right = mid - 1;}}return left - 1;}
}

相关文章:

【手撕数据结构】二分查找(好多细节)

&#x1f308;键盘敲烂&#xff0c;年薪30万&#x1f308; 目录 普通版本的二分查找&#xff1a; right只负责控制边界(少了两次比较)&#xff1a; 时间复杂度更稳定的版本&#xff1a; BSLeftmost&#xff1a; BSRightmost&#xff1a; 普通版本的二分查找&#xff1a; …...

Python+Selenium WebUI自动化框架 -- 基础操作封装

前言&#xff1a; 封装Selenium基本操作&#xff0c;让所有页面操作一键调用&#xff0c;让UI自动化框架脱离高成本、低效率时代&#xff0c;将用例的重用性贯彻到极致&#xff0c;让烦人的PO模型变得无所谓&#xff0c;让一个测试小白都能编写并实现自动化。 知识储备前提&a…...

PyCharm 【unsupported Python 3.1】

PyCharm2020.1版本&#xff0c;当添加虚拟环境发生异常&#xff1a; 原因&#xff1a;Pycharm版本低了&#xff01;不支持配置的虚拟环境版本 解决&#xff1a;下载PyCharm2021.1版本&#xff0c;进行配置成功&#xff01;...

flutter TabBar指示器

第一层tabView import package:jade/configs/PathConfig.dart; import package:jade/customWidget/MyCustomIndicator.dart; importpackage:jade/homePage/promotion/promotionPost/MyPromotionListMainDesc.dart; import package:jade/homePage/promotion/promotionPost/MyPr…...

PDF/X、PDF/A、PDF/E:有什么区别,为什么有这么多格式?

PDF 是一种通用文件格式&#xff0c;允许用户演示和共享文档&#xff0c;无论软件、硬件或操作系统如何。多年来&#xff0c;已经创建了多种 PDF 子类型来满足各个行业的不同需求。让我们看看一些最流行的格式&#xff1a;PDF/X、PDF/A 和 PDF/E。 FastReport .net下载 PDF/X …...

Microsoft发布了一份关于其产品安全修复的 11 月报告。

&#x1f47e; 平均每天有 50 多个漏洞被发现&#xff0c;其中一些会立即被网络犯罪分子利用。我们把那些现在很受网络犯罪分子欢迎&#xff0c;或者根据我们的预测&#xff0c;在不久的将来可能会被大量利用的漏洞称为趋势漏洞。 在攻击者开始利用这些漏洞之前 12 小时&#…...

12v24v60v高校同步降压转换芯片推荐

12V/24V/60V 高校同步降压转换芯片推荐&#xff1a; 对于需要高效、稳定、低噪音的降压转换芯片&#xff0c;推荐使用WD5030E和WD5105。这两款芯片都是采用同步整流技术&#xff0c;具有高效率、低噪音、低功耗等优点&#xff0c;适用于各种电子设备。 WD5030E是一款高效率…...

pip 问题

升级pip命令&#xff1a; python -m pip install --upgrade pippip不能下载pytorch&#xff1a; 这个问题我一直没解决。不知道有哪位大佬可以留言给我。把whl文件下载到本地也没有&#xff0c;pip不会进行本地文件夹搜索。...

云计算(一):弹性计算概述

云计算&#xff08;一&#xff09;&#xff1a;弹性计算概述 背景含义原理应用 背景 在实际场景中&#xff0c;经常会出现短时间内资源需求爆发式增长或长时间内资源需求不断增长&#xff0c;这时需要资源供给时刻满足需求的变化&#xff0c;保障业务正常运行。传统的供给方式…...

Qt/C++ 获取QProcess启动的第三方软件的窗体标题

Qt/C 获取QProcess启动的第三方软件的窗体标题&#xff0c;在使用EnumWindows获取窗体句柄(HWND)时&#xff0c;如果返回提前FALSE&#xff0c;则获取到的HWND状态IsWindow正常&#xff0c;但就是获取不到窗体标题。必须正常返回TRUE才能使用HWND获取到窗体标题&#xff0c;要不…...

Borland编辑器DOS系统快捷键应用

在项目中接触到DOS系统&#xff0c;该系统距离当下已经接近20年时间&#xff0c;网络上资源较少&#xff0c;因为需要用到C语言编辑器BorlandC,每次应用时难免会忘记快捷键使用&#xff0c;给使用造成很大的不便。 于是把现有收集的快捷键做出整理便于使用&#xff0c;供大家参…...

KeyarchOS的CentOS迁移实践:使用操作系统迁移工具X2Keyarch V2.0

KeyarchOS的CentOS迁移实践&#xff1a;使用操作系统迁移工具X2Keyarch V2.0 作者&#xff1a; 猫头虎博主 文章目录 KeyarchOS的CentOS迁移实践&#xff1a;使用操作系统迁移工具X2Keyarch V2.0&#x1f405;摘要引言1. 迁移前的精心准备1.1 系统环境介绍1.2 深度数据验证1.2.…...

Golang抓包:实现网络数据包捕获与分析

介绍 在网络通信中&#xff0c;网络数据包是信息传递的基本单位。抓包是一种监控和分析网络流量的方法&#xff0c;用于获取网络数据包并对其进行分析。在Golang中&#xff0c;我们可以借助现有的库来实现抓包功能&#xff0c;进一步对网络数据进行分析和处理。 本文将介绍如…...

分类预测 | Matlab实现QPSO-SVM、PSO-SVM、SVM多特征分类预测对比

分类预测 | Matlab实现QPSO-SVM、PSO-SVM、SVM多特征分类预测对比 目录 分类预测 | Matlab实现QPSO-SVM、PSO-SVM、SVM多特征分类预测对比分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现QPSO-SVM、PSO-SVM、SVM分类预测对比&#xff0c;运行环境Matlab2018b…...

kubernetes部署jenkins

参考&#xff1a;kubernetes 部署 Jenkins jenkins kubernetes pipeline_mob64ca14116c53的技术博客_51CTO博客 第七篇&#xff1a;kubernetes部署jenkins-CSDN博客 1、当前kubernetes集群已部署nfs服务 showmount -e 创建jenkins目录 2、添加jenkins的pvc kubectl create …...

Node.js详解

一、是什么 Node.js 是一个开源与跨平台的 JavaScript 运行时环境 在浏览器外运行 V8 JavaScript 引擎&#xff08;Google Chrome 的内核&#xff09;&#xff0c;利用事件驱动、非阻塞和异步输入输出模型等技术提高性能 可以理解为 Node.js 就是一个服务器端的、非阻塞式I/…...

v-html命令渲染的内容,使用scoped属性的情况下,样式不起作用

v-html命令渲染的内容&#xff0c;使用scoped属性的情况下&#xff0c;样式不起作用 如&#xff1a; CSS&#xff1a; <style scoped> .question_title_text img{ display: block; height: 200px; margin: 10px auto 0 auto;} </style> HTML&#xff1a; <d…...

浅谈vue2.0和vue3.0的区别

Vue3.0相对于Vue2.0有以下改进&#xff1a; Vue 3.0 是一个新版本的 Vue.js&#xff0c;它提供了更高效的渲染性能和更强大的工具链。下面是一些 Vue 3.0 的具体用法&#xff1a; 创建 Vue 实例&#xff1a;与 Vue 2.x 相同&#xff0c;使用 Vue.createApp() 方法创建 Vue 实例…...

git clone报错SSL connect error

解决CentOS 6.6上Git操作引发的SSL连接错误问题 最近在处理一个CentOS 6.6服务器上的问题时&#xff0c;遇到了一个比较棘手的问题。我的小伙伴在操作Git时&#xff0c;发现无法执行git pull命令&#xff0c;提示找不到Git组件。在这篇文章中&#xff0c;我会详细介绍我们是如…...

LeetCode(26)判断子序列【双指针】【简单】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 判断子序列 1.题目 给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...