【代码随想录 | 数组 01】二分查找

在这里插入图片描述

文章目录

  • 1.二分查找
    • 1.1题目
    • 1.2思路(核心:区间的定义)
    • 1.3左闭右闭
    • 1.4左闭右开
    • 1.5总结

1.二分查找

1.1题目

704.二分查找—力扣题目链接

  • 题目:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1
  • 示例一:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
  • 示例二:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

1.2思路(核心:区间的定义)

  1. 题目的前提是数组为有序数组,同时题目还强调 数组中无重复元素
  2. 因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。

1.3左闭右闭

  • 定义target在 [left, right] 区间,所以有如下两点:
  1. while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  2. if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1
  3. 下面举例演示:在一组有序,不重复数组中分别查找数据2、数据6的过程

image-20240310152650608

/*** @Description 二分查找第一种写法:左闭右闭* @Param* @Return 下标值:int*/public int binarySearch1(int[] arr,int target){int left=0;int right=arr.length-1;while(left<=right){/***  写法一:可能出现溢出情况*      int mid=(left+right)/2;*  写法二:*      int mid=left+(right-left)/2;*///写法三:右移运算符 代替 除号int mid=left+((right-left)>>1);if(arr[mid]>target){        //在左区间,即[left,mid-1]right=mid-1;}else if(arr[mid]<target){  //在右区间,即[mid+1,right]left=mid+1;}else{return mid;}}return -1;}
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

1.4左闭右开

如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

  1. while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  2. if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]大于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]

image-20240310155356483

  • 代码示例:
	/*** @Description 二分查找第一种写法:左闭右闭* @Param* @Return 下标值:int*/public int binarySearch2(int[] arr,int target){int left=0;int right=arr.length;while(left<right){int mid=left+((right-left)>>1);if(arr[mid]>target){        //在左区间,即[left,mid-1)right=mid;}else if(arr[mid]<target){  //在右区间,即[mid+1,righ)left=mid+1;}else{return mid;}}return -1;}
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

1.5总结

  • 使用二分查找的两个前提:
    • 数组有序
    • 数组元素唯一,不重复
  • 二分查找的两个写法区分:
左闭右闭左闭右开
right初始取值right=arr.length-1right=arr.length
循环条件while(left<=right)while(left<right)
left更新值(到右区间查找)left=mid+1left=mid+1
right更新值(到左区间查找)right=mid-1right=mid

在这里插入图片描述

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

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

相关文章

C语言分析基础排序算法——插入排序

目录 插入排序 直接插入排序 希尔排序 希尔排序基本思路解析 希尔排序优化思路解析 完整希尔排序文件 插入排序 直接插入排序 所谓直接插入排序&#xff0c;即每插入一个数据和之前的数据进行大小比较&#xff0c;如果较大放置在后面&#xff0c;较小放置在前面&#x…

LeetCode-102.题: 二叉树的层序遍历(原创)

【题目描述】 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]] 【题目链接…

【ICCV21】Swin Transformer: Hierarchical Vision Transformer using Shifted Windows

文章目录 0. Abstract1. Introduction2. Related Work3. Method3.1 Overall Architecture3.2 Shifted Window based Self-Attention3.3 Architecture Variants 4. Experiments4.1 Image Classification on ImageNet-1K4.2 Object Detection on COCO4.3 Semantic Segmentation o…

文本向量评测MTEB和C-MTEB

文章目录 简介MTEBC-MTEB参考资料 简介 MTEB(Massive Text Embedding Benchmark)是目前评测文本向量很重要的一个参考&#xff0c;其榜单也是各大文本向量模型用来展示与其他向量模型强弱的一个竞技台。 C-MTEB则是专门针对中文文本向量的评测基准。 MTEB MTEB的目的是为了…

OKLink2月安全月报| 2起典型漏洞攻击案例分析

在本月初我们发布的2024年2月安全月报中提到&#xff0c;2月全网累计造成损失约1.03亿美元。其中钓鱼诈骗事件损失占比11.76%。 OKLink提醒大家&#xff0c;在参与Web3项目时&#xff0c;应当仔细调研项目的真实性、可靠性&#xff0c;提升对钓鱼网站和风险项目的甄别能力&…

C语言从入门到熟悉------第二阶段

printf的用法 printf的格式有四种&#xff1a; &#xff08;1&#xff09;printf("字符串\n"); 其中\n表示换行的意思。其中n是“new line”的缩写&#xff0c;即“新的一行”。此外需要注意的是&#xff0c;printf中的双引号和后面的分号必须是在英文输入法下。双引…

portainer管理远程docker和docker-swarm集群

使用前请先安装docker和docker-compose&#xff0c;同时完成docker-swarm集群初始化 一、portainer-ce部署 部署portainer-ce实时管理本机docker&#xff0c;使用docker-compose一键拉起 docker-compose.yml version: 3 services:portainer:container_name: portainer#imag…

[机器视觉]halcon应用实例 找圆

[机器视觉]halcon应用实例 找圆 代码 *清空屏幕&#xff0c;显示控制图像 dev_close_window () dev_update_off () read_image (Image, 形状模板图) dev_open_window_fit_image (Image, 0, 0, -1, -1, WindowHandle) dev_display (Image) *创建测量模型 create_metrology_mod…

AD20新建工程步骤

1 新建工程 2 创建 3 新建原理图 4 新建PCB图 5 对原理图贺PCB都进行保存 6 新建原理图库贺PCB库&#xff0c;以及保存 最后在保存位置上都可以看到 打开的时候直接打开工程&#xff0c;它自己就会把这些链接在一起

UVa11595 Crossing Streets EXTREME

题目链接 UVa11595 - Crossing Streets EXTREME 题意 平面上有 n&#xff08;n≤35&#xff09;条直线&#xff0c;各代表一条街道。街道相互交叉&#xff0c;形成一些路段&#xff08;对应于几何上的线段&#xff09;。你的任务是设计一条从A到B的路线&#xff0c;使得穿过路…

c++: 引用能否替代指针? 详解引用与指针的区别.

文章目录 前言1. 引用和指针的最大区别:引用不能改变指向2. 引用和指针在底层上面是一样的3. 引用和指针在sizeof面前大小不同4. 有多级指针,没有多级引用5.引用是引用的实体,指针会向后偏移同一个类型的大小 总结 前言 新来的小伙伴如果不知道引用是什么?可以看我的上一篇文…

AI新工具(20240312) Midjourney官方发布角色一致性功能;免费且开源的简历制作工具;精确克隆语调、控制声音风格

1: Midjourney角色一致性功能 使人物画像在多方面高度一致成为可能。 Midjourney的角色一致性功能的使用方法如下&#xff1a; ⭐在你的输入指令后面加上 --cref URL&#xff0c;其中URL是你选择的角色图像的链接。 ⭐你可以通过 --cw 参数来调整参照的强度&#xff0c;范围…

spring boot 使用 webservice

spring boot 使用 webservice 使用 java 自带的 jax-ws 依赖 如果是jdk1.8,不需要引入任何依赖&#xff0c;如果大于1.8 <dependency><groupId>javax.jws</groupId><artifactId>javax.jws-api</artifactId><version>1.1</version&g…

【Linux】文件缓冲区|理解文件系统

目录 预备知识 观察现象 第一&#xff1a;携带\n&#xff0c;不使用fork()&#xff0c;打印到显示器 第二&#xff1a;携带\n&#xff0c;使用fork()&#xff0c;打印到显示器 第三&#xff1a;携带\n&#xff0c;使用fork()&#xff0c;打印到文件里 第四&#xff1a;不携…

案例分析篇03:一篇文章搞定软考设计模式考点(2024年软考高级系统架构设计师冲刺知识点总结系列文章)

专栏系列文章推荐: 2024高级系统架构设计师备考资料(高频考点&真题&经验)https://blog.csdn.net/seeker1994/category_12593400.html 【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】(2024年软考高级系统架构设计师冲刺知识点总结-案例分析篇-…

IPSec NAT穿越原理

一、IPSec VPN在NAT场景中存在的问题 当某些组网中&#xff0c;有的分支连动态的公网IP地址也没有&#xff0c;只能由网络中的NAT设备进行地址转换&#xff0c;才能访问互联网&#xff0c;然而IPsec是用来保护报文不被修改的&#xff0c;而NAT需要修改报文的IP地址&#xff0c…

十大排序算法(冒泡排序、插入排序、选择排序、希尔排序、堆排序、快排、归并排序、桶排序、计数排序、基数排序)

目录 一、冒泡排序&#xff1a; 二、插入排序&#xff1a; 三、选择排序&#xff1a; 四、希尔排序&#xff1a; 五、堆排序&#xff1a; 六、快速排序&#xff1a; 6.1挖坑法&#xff1a; 6.2左右指针法 6.3前后指针法&#xff1a; 七、归并排序&#xff1a; 八、桶…

力扣hot100:240.搜索二维矩阵II(脑子)

吉大21级算法分析与设计的一道大题&#xff0c;由于每一行都是排好序的直接逐行二分 可以达到&#xff1a;O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分&#xff1a; 在矩阵中用中心点比较&#xff0c;如果target大于中心点的值&#xff0c;则由于升序排列&am…

vue学习笔记23-组件事件⭐

组件事件 在组件的模板表达式中&#xff0c;可以直接使用$emit方法触发自定义事件&#xff1b;触发自定义事件的目的是组件之间传递数据 好好好今天又碰到问题了&#xff0c;来吧来吧 测试发现其他项目都可以 正常的run ,就它不行 搜索发现新建项目并进入以后&#xff0c;用指…

C语言--- 指针运算笔试题详解

目录 题目1&#xff1a; 题目2&#xff1a; 题目3&#xff1a; 题目4&#xff1a; 题目5&#xff1a; 题目6&#xff1a; 题目7&#xff1a; 题目1&#xff1a; #include <stdio.h> int main() {int a[5] { 1, 2, 3, 4, 5 };int *ptr (int *)(&a 1);print…