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

算法 - 二分查找

算法 - 二分查找

今天继续八股文学习,看一下比较常规的几个算法

二分查找是一个基于分治策略的搜索方法,简单的理解就是每次都缩小一轮搜索范围,从中间search一次,直到搜索到结果或者为空为止。

基本思路(设一个有序的数组为nums,需要查询的值是target)

  1. 设置 i = 0,j = n -1。i就是数组开头的第一个索引值,j就是最后一个索引值。
  2. 如果i > j 了,证明查询结束了没有找到结果。
  3. 然后设置一个值为m,这个m就是减少的搜索范围(应该说成是每次拿数组中间的那个值,数组的中间索引),m = (i + j )/ 2 ,有的时候会有小数,所以这个时候需要取整。
  4. 如果target的值小于数组中间的值(也就是索引值是m的值),那就意味着这个值在中间值的左边(数组中间的靠左的位置),所以 j = m - 1,数组的最大值挪到了中间值靠左的位置,然后我们再重复回到第二步继续跑。
  5. 如果target的值大于数组中间的值,意味着这个值在中间值的右边,所以 i = m + 1,数组的最小值挪到了中间值靠右的位置,然后再重复回到第二步继续跑。
  6. 当索引值m = target的时候,就直接return返回查询的结果值。
/*** 二分查找* <p>* 基于分治策略的的高效搜索方法。* <p>* 每轮都缩小一般的搜索范围,直到搜索到结果或者区间的结果为空的时候停止。*/
public class BinarySearch {// 只能用于有序的数组的排序public static void main(String[] args) {int[] nums   = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int   target = 11;System.out.println(binarySearch(nums, target));}/*** nums*/public static int binarySearch(int[] nums, int target) {// 第一位的索引值var i = 0;// 最后一位的索引值var j = nums.length - 1;while (i <= j) {// 先拿一个中间点,并且需要取整,因为有时候可能回出现小数点int m = i + (j - i) / 2;// 如果中间值的小于目标值,则往中间值的左边靠if (nums[m] < target) {i = m + 1;} else if (nums[m] > target) { // 如果中间值大于目标值,则往中间值的右边靠j = m - 1;} else {return m;}}// 如果找不到元素返回 -1return -1;}
}

优点

在时间和空间方面都有较好的性能。

二分查找的时间效率高,不需要额外的空间。

局限性

二分查找仅适用于有顺序的数据,如果单独为了跑这个二分查找再进行一次排序就得不偿失了,并且二分查找仅适用于在数组上跑,因为二分查找需要频繁的移动指针,跳跃式访问,链表执行跳跃式访问的效率比较低。当数据量小的时候使用线性查找比二分查找的效率要高。(下一篇写一下线性查找)

相关文章:

算法 - 二分查找

算法 - 二分查找 今天继续八股文学习&#xff0c;看一下比较常规的几个算法 二分查找是一个基于分治策略的搜索方法&#xff0c;简单的理解就是每次都缩小一轮搜索范围&#xff0c;从中间search一次&#xff0c;直到搜索到结果或者为空为止。 基本思路&#xff08;设一个有序的…...

Python知识点:如何使用Python进行图像批处理

在Python中进行图像批处理可以使用多种库&#xff0c;如 Pillow、OpenCV 和 imageio。这些库可以用来执行各种图像处理任务&#xff0c;如调整大小、裁剪、旋转、滤镜应用等。以下是使用这些库进行图像批处理的示例。 使用 Pillow 进行图像批处理 Pillow 是一个功能强大的图像…...

数据结构实验1

实验题1&#xff1a;求1到n的连续整数和 题目描述 编写一个程序,对于给定的正整数n,求12…十n,采用逐个累加与(n1)/2(高斯法)两种解法。对于相同的n,给出这两种解法的求和结果和求解时间,并用相关数据进行测试。 运行代码 //实验题1&#xff1a;求1到n的连续整数和 #includ…...

使用Postman+JMeter进行简单的接口测试

以前每次学习接口测试都是百度&#xff0c;查看相关人员的实战经验&#xff0c;没有结合自己公司项目接口真正具体情况。 这里简单分享一下公司项目Web平台的一个查询接口&#xff0c;我会使用2种工具Postman和JMeter如何对同一个接口做调试。 准备工作 首先&#xff0c;登录公…...

基于 SpringBoot 的车辆充电桩管理系统

专业团队&#xff0c;咨询就送开题报告 摘 要 随着信息化时代的到来&#xff0c;管理系统都趋向于智能化、系统化&#xff0c;车辆充电桩管理系统也不例外&#xff0c;但目前国内仍都使用人工管理&#xff0c;市场规模越来越大&#xff0c;同时信息量也越来越庞大&#xff0c;…...

centos7.9安装clamav教程

本章教程主要记录在centos7.9安装clamav过程。 ClamAV(Clam AntiVirus)是一个开源的防病毒软件工具,主要用于检测和消除恶意软件。它最初由 Tomasz Kojm 于 2001 年开发,并由 Cisco Systems 维护和支持。ClamAV 广泛应用于邮件网关、文件服务器和其他需要防病毒保护的环境中…...

产品经理如何转型为AI产品经理,如何理解AI产品工程化

技术领域,特别是人工智能和机器学习,其优秀模型的成功应用是一个复杂过程,它不仅要求技术本身的卓越,还须与现有解决方案竞争,这涉及到技术成熟度、成本有效性、市场接受度等多维度因素。 在这一过程中,产品经理扮演着核心角色,负责协调各方利益,确保技术能够转化为满…...

TiDB从0到1学习笔记(精华篇)

历时四个月&#xff0c;恭喜赵老师的《TiDB从0到1》 系列文章顺利完结&#xff0c;小编再次梳理一遍文稿&#xff0c;并附注解分享给大家。 整体架构 从 TiDB 1.0 到 8.0&#xff0c;TiDB 的体系结构一直在不断演进。接下来让我们一起看看整体架构的变化。 TiDB v1 TiDB v1&…...

NLP-新词挖掘

一、背景 网络领域的新词发现&#xff08;挖掘&#xff09;是一个非常重要的nlp课题。在处理文本对象时&#xff0c;非常关键的问题在于“切词”这个环节&#xff0c;几乎所有的后续结果都依赖第一步的切词。因此切词的准确性在很大程度上影响着后续的处理&#xff0c;切词结果…...

电脑录屏不求人,9月必备免费录屏软件推荐!苹果电脑可用!

在当今这个信息爆炸的时代&#xff0c;电脑录屏软件已经成为了我们日常工作和生活中不可或缺的工具。无论是制作教学视频、录制在线课程、游戏直播&#xff0c;还是创建产品演示&#xff0c;一个好的录屏软件都能帮助我们更高效地完成任务。市场上的录屏软件琳琅满目&#xff0…...

SpringMVC基于注解使用:国际化

01-国际化介绍 首先在bootstrap下载个页面 下载后把登录页面的代码粘上去 然后再登录页面代码上有些超链接需要再spring-mvc.xml里面配置下&#xff0c;登录页面才能正常显示 配置静态资源 国际化-根据浏览器语言国际化 现在是中文的情况&#xff0c;要改为英文 1.配置下属…...

工地安全帽检测系统源码分享

工地安全帽检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer V…...

如何为 DigitalOcean 静态路由操作员设置故障转移

静态路由操作器的主要目的是提供更大的灵活性&#xff0c;并在 Kubernetes 环境中控制网络流量。它使你能够根据应用程序的需求自定义路由配置&#xff0c;从而优化网络性能。该操作器作为 DaemonSet 部署&#xff0c;因此将在你的 DigitalOcean Managed Kubernetes 集群的每个…...

Ansible简单部署与使用

目录 环境安装Ansibleapt installmarkupsafe error 配置Ansible创建个人目录ansible.cfghosts 测试Ansibleping批量执行自定义命令 环境 Ubuntu 20.04 安装Ansible apt install sudo apt install ansiblemarkupsafe error 安装成功后&#xff0c;尝试运行ansible&#xff…...

Harmony Next charles 抓包指南

1.选择安装移动证书 代理信息如下 2.设置手机代理 手机与电脑连接同一网络&#xff0c;然后配置步骤 1 的代理 路径&#xff1a;设置-wlan-选择当前网络编辑-代理-保存 注意&#xff1a;手机配置代理后&#xff0c;目前会默认断开连接&#xff0c;需要手动再连接下 wifi 3.鸿…...

【HarmonyOS】Beta最新对外版本IDE下载和环境配置

【HarmonyOS】Beta最新对外版本IDE下载和环境配置 前言 目前华为HarmonyOS的系统版本已经从Develop Beta升级为Beta预览版&#xff0c;全面开放。再也不需要白名单限制&#xff0c;才能下载使用最新的IDE和预览最新的开放文档了。 IDE下载和安装 Beta IDE下载地址 1.根据你…...

2024年9月第2周AI资讯

阅读时间&#xff1a;3-4min 更新时间&#xff1a;2024.9.9-2024.9.13 目录 Groq推出多模态大模型LLaVA v1.5 7B AI通过重读问题可以变得更聪明 美国Weave公司发布Isaac多功能个人机器人 特斯拉机器人出租车将实现无线充电 Adobe视频编辑新时代 无人驾驶汽车超越人类 AI…...

【软件使用-MEGA】构建进化树报错

*_summary.txt报错&#xff1a; MEGA-CC 10.2.6 Molecular Evolutionary Genetics Analysis Build#: 10210527-x86_640% Reading distance matrix MEGA-CC has logged the following error:When 2024年09月13日 下午 01时32分49秒 下午Data …...

面试常见八股

JAVA篇 基础 1、自动拆箱和装箱 装箱&#xff1a;装箱是将值类型&#xff08;如int、double、struct等&#xff09;转换为object类型或任何接口类型的过程。由于object是所有类型的基类&#xff08;在.NET中&#xff09;&#xff0c;并且接口是引用类型&#xff0c;因此装箱…...

第十八章 番外 余弦相似度

余弦相似度&#xff08;Cosine Similarity&#xff09;是一种衡量两个非零向量之间角度的度量方式&#xff0c;用于评估它们之间的相似性。它的值范围从 -1 到 1&#xff0c;其中 1 表示完全相同的方向&#xff08;即向量完全相同&#xff09;&#xff0c;0 表示正交&#xff0…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...