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

Java 算法篇-深入了解二分查找法

🔥博客主页: 小扳_-CSDN博客
❤感谢大家点赞👍收藏⭐评论✍
  

 

目录

        1.0 二分查找法的说明

        2.0 二分查找实现的多种版本

        2.1 二分查找的基础版本

        2.2 二分查找的改动版本

        2.3 二分查找的平衡版本

        2.4 二分查找的官方版本

        3.0 二分查找的应用


        1.0 二分查找法的说明

        二分查找法(Binary Search)是一种在有序数组有序列表中查找特定元素的搜索算法。其基本思想是将数组或列表分成两部分,取中间位置的元素进行比较,若该元素等于目标值,则查找成功若该元素大于目标值,则在左半部分继续查找若该元素小于目标值,则在右半部分继续查找。不断重复这个过程,直到找到目标值或查找范围缩小到只剩下一个元素为止。

        需要重点注意的是,使用二分查找的前提必须是数组是有序的或者列表是有序的。

        2.0 二分查找实现的多种版本

        基本来说可以分为基础版本和改动版本、平衡版、官方版本。

        2.1 二分查找的基础版本

        先来讲讲具体的实现吧,需要一个有序的数组 arr[] 或者有序列表,还有拿到需要查找的目标元素 int target

        需要定义一下三种变量:

        第一种,int left ;一开始记录着是最左边的元素的索引,即为 0.

        第二种,int right;一开始记录着是最右边的元素的索引,即为 array.length - 1

        第三种,int mid;记录着是中间的元素的索引,即为(left + right)>>> 1;

        接着先要用 arr[mid] 的元素与 target 进行对比,这时候就会有三种情况,分别做不同的处理,假如 if(arr[mid] < target ),中间的元素小于目标元素时,要对 left 进行 left = mid + 1处理,假如 if(arr[mid] > target ),中间的元素大于目标元素时,要对 right 进行 right = mid - 1处理,假如 if(arr[mid] = target ),这时候就找到了目标元素了,直接返回 mid ,因此这是一个循环的过程,不断缩小范围来寻找目标元素,这一切都需要满足 left <= right 这个条件。

具体代码实现如下:

public class BinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 3;System.out.println(search(arr, target));}public static int search(int[] arr, int target){int left = 0;int right = arr.length - 1;while (left <= right){int mid = (left + right) >>> 1;if (arr[mid] < target){left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;}else {return mid;}}return -1;}
}

运行结果如下:

        目标元素3的索引为1,补充一下,若没有找到的话,这里定义返回为 -1 。

        2.2 二分查找的改动版本

        这个版本在基础版本的基础上进行了三点改动:

        第一点;int right;一开始记录着是最右边的元素的索引,即为 array.length 。

        注意,在基础版本中是需要减1的,而这里直接取元素个数,当然我们都知道这个会出现越界情况,所以才会有第二点改动 。

        第二点;这一切都需要满足 left < right 这个条件。

        这基础版本中循环条件是需要 <= 的条件,这里就不需要了,来分析一下为什么呢?

        原因就在第一点,在 right 索引下的元素是不可取的,重点在<不可取>,仔细品味一下,无论right 在之后的循环中得到的所有索引都是不可取到的元素。

        第三点;假如 if(arr[mid] > target ),中间的元素大于目标元素时,要对 right 进行 right = mid 处理。

具体代码实现如下:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 3;System.out.println(search(arr, target));}public static int search(int[] arr, int target) {int left = 0;int right = arr.length;while (left < right) {int mid = (left + right) >>> 1;if (arr[mid] < target) {left = mid + 1;} else if (target < arr[mid]) {right = mid;} else {return mid;}}return -1;}
}

运行结果如下:

         2.3 二分查找的平衡版本

        相对比与第一、两种,这个版本的效率会更高一点。这种版本的思路就是将范围不断缩小为1,然后获取 left 索引下的元素,来判断是否等于目标元素。

具体代码如下:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 3;System.out.println(search(arr, target));}public static int search (int[] arr, int target){int left = 0;int right = arr.length;while (1 < right - left){int mid = (left + right) >>> 1;if (target < arr[mid]){right = mid;} else  {left = mid;}}if (arr[left] == target){return left;}else {return -1;}}
}

运行结果如下:

        2.4 二分查找的官方版本

直接来看原代码:

        来分析一下,从总体来看,官方的二分查找的实现跟第一种的基本版本是大致相同的,有一点跟基础版本的不同的是,就是返回值。在基础版本中,如果找不到就返回 -1,而这里返回的是 -(low + 1),接下来具体讲解一下。

        第一点low 代表的是插入点,这个值跟 left 的值是一样的。

        第二点,关于负数的说法,一般来说找不到的元素时,会返回负数。

具体代码的实现:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,3,5,7,9,11};int target = 2;System.out.println(search(arr, target));}public static int search(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = (left + right) >>> 1;if (arr[mid] < target) {left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;} else {return mid;}}return -(left + 1);}
}

运行结果如下:

        来算一下,我们知道 2 在数组中是不存在的,插入点为 1 ,则-(1+1)==  -2,验证了是符合的结果的。

 

        3.0 二分查找的应用

        给出下列数组 int[] arr {1,2,3,3,3,3,5,6,7} 要求返回目标元素3的起始位置与结束位置。

        实现的思路:先找起始位置,首先得先找到目标元素的索引,之后得往左边去找找结束位置也是同理,首先得先找到目标元素的索引,之后得往右边去找

代码如下:

public class NewBinarySearch {public static void main(String[] args) {int[] arr = {1,2,3,3,3,3,5,6,7};int target = 3;System.out.print(findLeft(arr, 3)+" ");System.out.println(findRight(arr, 3));}public static int findLeft(int[] arr,int target){int left = 0;int right = arr.length - 1;int sign = -1;while (left <= right){int mid = (left + right) >>> 1;if (arr[mid] < target){left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;}else {sign = mid;right = mid - 1;}}return sign;}public static int findRight(int[] arr, int target){int left = 0;int right = arr.length - 1;int sign = -1;while (left <= right){int mid = (left + right) >>> 1;if (arr[mid] < target){left = mid + 1;} else if (target < arr[mid]) {right = mid - 1;}else {sign = mid;left = mid + 1;}}return sign;}
}

运行结果如下:

 

相关文章:

Java 算法篇-深入了解二分查找法

&#x1f525;博客主页&#xff1a; 小扳_-CSDN博客 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 目录 1.0 二分查找法的说明 2.0 二分查找实现的多种版本 2.1 二分查找的基础版本 2.2 二分查找的改动版本 2.3 二分查找的平衡版本 2.4 二分查找的官方版本 3.0 二分查找的应用 1…...

Data-Centric Financial Large Language Models

本文是LLM系列文章&#xff0c;针对《Data-Centric Financial Large Language Models》的翻译。 以数据为中心的大语言金融模型 摘要1 引言2 背景3 方法4 实验5 结论和未来工作 摘要 大型语言模型&#xff08;LLM&#xff09;有望用于自然语言任务&#xff0c;但在直接应用于…...

【HarmonyOS】服务卡片 API6 JSUI跳转不同页面并携带参数

【关键字】 服务卡片、卡片跳转不同页面、卡片跳转页面携带参数 【写在前面】 本篇文章主要介绍开发服务卡片时&#xff0c;如何实现卡片点击跳转不同页面&#xff0c;并携带动态参数到js页面。在此篇文章“服务卡片 API6 JSUI跳转不同页面”中说明了如果跳转不同页面&#xf…...

SQL server数据库端口访问法

最近数据库连接&#xff0c;也是无意中发现了这个问题&#xff0c;数据库可根据端口来连接 网址:yii666.com< 我用的是sql2014测试的&#xff0c;在安装其他程序是默认安装了sql(sql的tcp/ip端口为xxx)&#xff0c;服务也不相同&#xff0c;但是由于比较不全&#xff0c;我…...

深孔枪钻厂家,科研管理系统思路

序号 名称 参数及技术指标 &#xff08;一&#xff09;系统性能要求 1&#xff0e;系统界面&#xff1a;支持中英文界面自由切换。 2. 系统兼容性&#xff1a;支持主流浏览器&#xff0c;如&#xff1a;IE11 以上、 360 安全浏览器、Firefox、Google Ch…...

【论文阅读笔记】GLM-130B: AN OPEN BILINGUAL PRE-TRAINEDMODEL

Glm-130b:开放式双语预训练模型 摘要 我们介绍了GLM-130B&#xff0c;一个具有1300亿个参数的双语(英语和汉语)预训练语言模型。这是一个至少与GPT-3(达芬奇)一样好的100b规模模型的开源尝试&#xff0c;并揭示了如何成功地对这种规模的模型进行预训练。在这一过程中&#xff0…...

Object常用方法

Object常用方法目录 1. equals(Object obj)&#xff1a; 2. toString()&#xff1a; 3. hashCode()&#xff1a; 4. getClass()&#xff1a; 5. notify() 和 notifyAll()&#xff1a; 6. wait() 和 wait(long timeout)&#xff1a; 7. clone()&#xff1a; 8. fina…...

【VR开发】【Unity】【VRTK】2-关于VR的基础知识

【概述】 在VRTK的实操讲解之前&#xff0c;本篇先介绍几个重要的VR认识。 【VR对各个行业的颠覆】 如果互联网几乎把所有行业都重做了一遍&#xff0c;VR在接下来的几年很可能再把现有的行业都重做一遍&#xff0c;包括但不限于教育&#xff0c;房地产&#xff0c;零售&…...

jeecg-uniapp 转成小程序的过程 以及报错 uniapp点击事件

uniapp 点击事件 tap: 单击事件 confirm: 回车事件 blur:失去焦点事件 touchstart: 触摸开始事件 touchmove: 触摸移动事件。 touchend: 触摸结束事件。 longpress: 长按事件。 input: 输入框内容变化事件。 change: 表单元素值变化事件。 submit: 表单提交事件。 scroll: 滚动…...

Django的静态文件目录(路径)如何配置?

通常用下面的三条语句配置Django的静态文件目录 STATICFILES_DIRS [os.path.join(BASE_DIR, static)] STATIC_URL /static/ STATIC_ROOT os.path.join(BASE_DIR, /static)那么这三条语句分别的作用是什么呢&#xff1f; 请参考博文 https://blog.csdn.net/wenhao_ir/articl…...

函数应用(MySQL)

--数值类函数 --绝对值 select abs(-1) --seiling ceil 向上取整 select ceil(1.1) --floor 向下取整 select floor(1.9); --四舍五入 select round(1.17, 1); --rand 随机数 select rand(rand()*1000); --字符串函数 utf8mb3 utfmb4 select length(小三) --查找字符数…...

数据分析过程中,发现数值缺失,怎么办?

按照数据缺失机制&#xff0c;数据分析过程中&#xff0c;我们可以将其分为以下几类&#xff1a; &#xff08;1&#xff09;完全随机缺失&#xff08;MCAR&#xff09;&#xff1a;所缺失的数据发生的概率既与已观察到的数据无关&#xff0c;也与未观察到的数据无关。 &#x…...

Vue3.0 toRef toRefs :VCA模式

简介 作用&#xff1a; 创建一个ref对象&#xff0c;其value值指向另一个对象中的某个属性 语法&#xff1a; const name toRef(person, name) 应用&#xff1a; 要将响应式对象中的某个属性单独供应给外部使用时 扩展&#xff1a; toRefs与toRef功能一致&#xff0c;但可…...

VS Code提取扩展时出错。XHR failed

需求&#xff1a;想要在扩展中心下载插件&#xff0c;发现报错 原因&#xff1a;vs code之前设置了代理&#xff0c;需要删除即可...

大模型需要哪类服务器

大模型需要高性能的服务器&#xff0c;以支持大规模的计算和存储需求。一般来说&#xff0c;大模型需要以下类型的服务器&#xff1a; 大型机&#xff1a;大型机可以提供强大的计算能力&#xff0c;适合处理大规模的数据和复杂的计算任务。 GPU服务器&#xff1a;GPU服务器可以…...

Java进阶(List)——面试时List常见问题解读 结合源码分析

前言 List、Set、HashMap作为Java中常用的集合&#xff0c;需要深入认识其原理和特性。 本篇博客介绍常见的关于Java中List集合的面试问题&#xff0c;结合源码分析题目背后的知识点。 关于的Set的博客文章如下&#xff1a; Java进阶&#xff08;Set&#xff09;——面试时…...

0基础学习PyFlink——个数滑动窗口(Sliding Count Windows)

大纲 滑动&#xff08;Sliding&#xff09;和滚动&#xff08;Tumbling&#xff09;的区别样例窗口为2&#xff0c;滑动距离为1窗口为3&#xff0c;滑动距离为1窗口为3&#xff0c;滑动距离为2窗口为3&#xff0c;滑动距离为3 完整代码参考资料 在 《0基础学习PyFlink——个数…...

vue3+ts 提取公共方法

因为好多页面都会使用到这个效验规则&#xff0c;封装一个校检规则&#xff0c;方便维护 封装前 封装后...

C++ ->

C -> 是访问类或结构体对象的成员的运算符 注意这里不是直接的访问.是用于访问指向对象的指针的成员 下面的代码可以很好的理解如下&#xff1a; #include<iostream>using namespace std;class Func{public:int i,j;void myFunc(){cout<<"i"<&l…...

VR全景在医院的应用:缓和医患矛盾、提升医院形象

医患关系一直以来都是较为激烈的&#xff0c;包括制度的不完善、医疗资源紧张等问题也时有存在&#xff0c;为了缓解医患矛盾&#xff0c;不仅要提升患者以及家属对于医院的认知&#xff0c;还需要完善医疗制度&#xff0c;提高医疗资源的配置效率&#xff0c;提高服务质量。 因…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...