二分查找怎么写? 你真的弄懂二分查找了吗

news/2024/4/19 0:24:06

大家好,我是三叔,很高兴这期又和大家见面了,一个奋斗在互联网的打工人。

二分查找是一种高效的查找算法,也是Java中最基础的算法之一,常用于已排序数组中的元素查找。本篇博客将介绍二分查找的原理、应用场景以及实现细节,帮助读者深入理解并掌握这一经典算法。它的核心思想是通过将查找区间逐渐缩小一半的方式,快速定位目标元素所在的位置。在大规模数据集上,二分查找的效率远高于线性查找。

大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

原理

二分查找的基本原理很简单:对于一个有序数组,从中间位置开始比较目标值和中间元素的大小关系,根据比较结果决定继续在左侧还是右侧继续查找。每次比较后,查找范围缩小一半,直到找到目标元素或确定目标元素不存在。

二分查找的原理如下:

  1. 初始化左边界 left 和右边界 right,分别指向数组的起始和末尾位置,定义好边界的开和闭
  2. 当 left <= right 时,进行循环查找;
  3. 计算中间位置 mid,即 mid = left + (right - left) / 2;
  4. 如果目标值target = 中间元素 array[mid],则返回 mid;
  5. 如果目标值target < 中间元素 array[mid],则在左半部分继续查找,更新右边界 right = mid - 1;
  6. 如果目标值target > 中间元素 array[mid],则在右半部分继续查找,更新左边界 left = mid + 1;
  7. 重复步骤 2-6,直到找到为止,不存在则返回一个自定义的值即可。

不废话,上代码:

// 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;// 定义区间 【left,right】while(left <= right) {// 计算中间位置,防止溢出,用减法int middle = left + (right - left) / 2;if(nums[middle] > target) {// 目标值小于中间值,在左边right = middle - 1;} else if (nums[middle] < target) {// 目标值大于中间值,在右边left = middle + 1;} else {// 刚好等于中间值,returnreturn  middle;}}return -1;}
}

需要注意的点

  1. 数组必须是有序的:二分查找要求在查找前,数组必须是按升序或降序排列的,否则无法正确找到目标元素。

  2. 左右边界的更新:在每次循环中,根据目标值和中间元素的大小关系,需要更新左右边界的值,缩小查找范围。

  3. 循环终止条件:循环终止的条件是左边界大于右边界,表示整个数组已经遍历完仍未找到目标元素。

  4. 中间位置的计算:中间位置的计算需要注意整型溢出的问题,通常采用 (left + right) / 2 或 left + (right - left) / 2 的方式来计算中间位置,避免溢出。

最后

二分查找是一种高效的查找算法,适用于已排序的数组或列表。它通过不断缩小查找范围的方式,在时间复杂度为 O(log n) 的情况下,定位目标元素target的位置。在实际应用中,需要注意数组的有序性、边界的更新和循环终止条件。


http://www.ppmy.cn/news/73380.html

相关文章

多目标优化算法求解无人机三维路径规划

一、无人机模型 无人机三维路径规划是无人机在执行任务过程中的非常关键的环节&#xff0c;无人机三维路径规划的主要目的是在满足任务需求和自主飞行约束的基础上&#xff0c;计算出发点和目标点之间的最佳航路。 1.1路径成本 无人机三维路径规划的首要目标是寻找起飞点和目…

tomcat加载顺序

一、 1、启动一个WEB项目的时候&#xff0c;WEB容器会去读取它的配置文件web.xml&#xff0c;读取<listener>和<context-param>两个结点。 2、紧急着&#xff0c;容创建一个ServletContext&#xff08;servlet上下文&#xff09;&#xff0c;这个web项目的所有部…

C++应届生程序员进入公司需要注意的五个细节,希望对大家有帮助

今天想跟大家分享一下应届C程序员实习生在进入公司后需要注意哪些问题。 C程序员是一种非常重要的职业&#xff0c;主要负责使用C语言编写各种软件程序。C是一种面向对象的编程语言&#xff0c;常用于开发操作系统、游戏引擎、嵌入式系统、图像处理等领域。因此&#xff0c;C程…

秘塔写作猫

秘塔写作猫是集AI智能写作、多人协作、改写润色、文本校对等功能为一体的AI原生创作平台&#xff0c;可以帮助不同群体大幅提升写作效率和生产力。 接下来小编就带大家了解一下该软件具体的一些功能&#xff0c;不论你是学生、上班族还是自媒体从业者等&#xff0c;该工具绝对可…

【Linux】ko文件查询内部信息方法

objdump命令 在 Linux 中&#xff0c;可以使用 objdump 命令来反汇编 ko 文件并查看其中的宏定义值。 以下是如何使用 objdump 命令查看 ko 文件中的宏定义值的示例&#xff1a; objdump -d <ko文件> | grep <宏名称>其中&#xff0c;-d 参数表示反汇编目标文件…

【物联网技术对生活的影响与展望】

随着科技日新月异的发展&#xff0c;物联网&#xff08;IoT&#xff09;技术正在快速地影响着我们的生活。它是将各种设备和物品连接在一起&#xff0c;通过互联网使它们可以相互交流和传递数据的技术。它的应用范围广泛&#xff0c;可以涵盖从智能家居到工业网络的各个领域。 …

2-《Java进阶》

[TOC](2-《Java进阶》 一. java多线程&#xff08;非常重要&#xff09;1.1. 线程java多线程实现方式主要有&#xff1a;1.继承Thread 2.实现Runnable3.实现CallableRunnable 与 Callable的区别&#xff1a;1.2. 线程的状态有哪些&#xff1f;1.3. 线程的状态转换及控制1.4. Ja…

ES6中Promise对象

1.Promise 说明&#xff1a;Promise是异步编程的一种解决方案。简而言之&#xff0c;也就是存者未来发生的事件的容器。 Promise提供统一的API,各种异步操作都可以用同样的方法进行处理。 特点&#xff1a;对象的状态不受外界影响。Promise对象代表一个异步操作&#xff0c;存…

Linux MISC 驱动实验

misc 的意思是混合、杂项的&#xff0c;因此 MISC 驱动也叫做杂项驱动&#xff0c;也就是当我们板子上的某 些外设无法进行分类的时候就可以使用 MISC 驱动。MISC 驱动其实就是最简单的字符设备驱 动&#xff0c;通常嵌套在 platform 总线驱动中&#xff0c;实现复杂的驱动。 M…

Less和sass安装及使用

CSS预处理器 由来 CSS本身不是一种编程语言。你可以用它开发网页样式&#xff0c;但是没法用它编程。换句话说&#xff0c;CSS基本上是设计师的工具&#xff0c;不是程序员的工具。它并不像其它程序语言&#xff0c;比如说JavaScript等&#xff0c;有自己的变量、常量、条件语…

C#中使用git将项目代码上传到远程仓库的操作

一、远程仓库创建操作&#xff08;远程仓库使用的是gitHub&#xff09; 1、登录GitHub官网&#xff0c;注册登录账号后&#xff0c;点击创建仓库 2、仓库名称命名&#xff0c;如下所示&#xff1a; 3、创建成功如下所示&#xff1a;获得https协议&#xff08;https://github.c…

JuiceFS 在多云存储架构中的应用 | 深势科技分享

2020 年末&#xff0c;谷歌旗下 DeepMind 研发的 AI 程序 AlphaFold2 在国际蛋白质结构预测竞赛上取得惊人的准确度&#xff0c;使得 “AI 预测蛋白质结构” 这一领域受到了空前的关注。今天我们邀请到同领域企业&#xff0c;深势科技为大家分享其搭建基础平台时的实践与思考。…

在阿里做了6年软件测试,4月无情被辞,想给划水的兄弟提个醒

先简单交代一下背景吧&#xff0c;某不知名 985 的本硕&#xff0c;17 年毕业加入阿里&#xff0c;以“人员优化”的名义无情被裁员&#xff0c;之后跳槽到了有赞&#xff0c;一直从事软件测试的工作。之前没有实习经历&#xff0c;算是6年的工作经验吧。 这6年之间完成了一次…

python 图片保存成视频

&#x1f468;‍&#x1f4bb;个人简介&#xff1a; 深度学习图像领域工作者 &#x1f389;工作总结链接&#xff1a;https://blog.csdn.net/qq_28949847/article/details/128552785 链接中主要是个人工作的总结&#xff0c;每个链接都是一些常用demo&#xff0c…

洛谷 池塘计数 floor-fill BFS 模板题

&#x1f351; OJ专栏 &#x1f351; P1596 Lake Counting 题面翻译 由于近期的降雨&#xff0c;雨水汇集在农民约翰的田地不同的地方。我们用一个 N M ( 1 ≤ N ≤ 100 , 1 ≤ M ≤ 100 ) N\times M(1\leq N\leq 100, 1\leq M\leq 100) NM(1≤N≤100,1≤M≤100) 的网格图表…

Qt——Qt控件之显示窗口-QLabel标签控件的使用总结(例程:QLabel显示文本标签及图片)

【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》

【CSS 选择器应用在QSS】第二天

CSS 选择器应用在QSS 【1】元素选择器&#xff08;元素通用性&#xff09;【2】id 选择器&#xff08;唯一性&#xff09;【2.1】CSS【2.2】QSS 【3】类选择器【3.1】CSS【3.2】QSS 【4】类选择器&#xff08;只针对指定元素&#xff09;【4.1】CSS【4.2】QSS 【5】通用选择器【…

语音合成工具_bark

1 介绍 多语言的文字转语音模型。 地址: https://github.com/suno-ai/bark 2 模型原理 Bark通过三个Transformer模型&#xff0c;将文本转换为音频。 2.1 文本到语义Token 输入&#xff1a;由Hugging Face的BERT标记器分词的文本 输出&#xff1a;编码生成音频的语义Token…

【面试高频 time: 2023-5-18】做分布式文件存储,如何保证分布式存储的高性能与高可用?

大家可以想到基本就是副本备份、双活、多活这种架构 在系统中通过复制协议将数据同步到多个存储节点&#xff0c;并确 保多个副本之间的数据⼀致性&#xff0c;当某个存储节点出故障 时&#xff0c;系统能够⾃动将服务切换到其他的副本 在分布式存储中⾼性能与⾼可⽤是⽭盾的&…

手把手教你怎么搭建自己的ChatGPT和Midjourney绘图(含源码)

AI程序采用NUXT3LARAVEL9开发&#xff08;目前版本V1.1.7&#xff09; 授权方式&#xff1a;三个顶级域名两次更换 1.AI智能对话-对接官方和官方反代&#xff08;markdown输出&#xff09;PS:采用百度与自用库检测文字 2.AI绘图-根据关键词绘图-增加dreamStudio绘画-增加mid…