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

《二分查找算法:在有序数组中搜索目标值》

目录

一、问题分析

二、二分查找算法原理

三、代码实现


给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target,我们要写一个函数来搜索 nums 中的 target,如果目标值存在就返回它的下标,否则返回 -1。

一、问题分析

既然数组是有序的,那么我们自然而然地会想到一种高效的查找算法 —— 二分查找(Binary Search)。二分查找的基本思想是将查找区间不断缩小一半,直到找到目标元素或者确定目标元素不存在为止。

二、二分查找算法原理

  1. 首先,我们确定查找区间的左右边界。初始时,左边界 left 为 0,右边界 right 为数组的长度 n - 1
  2. 然后,在每一轮查找中,我们计算中间元素的下标 mid,计算公式为 mid = left + (right - left) // 2。这里使用 left + (right - left) // 2 而不是简单的 (left + right) // 2 是为了避免在 left 和 right 很大时出现整数溢出的情况。
  3. 接下来,我们比较中间元素 nums[mid] 和目标值 target
    • 如果 nums[mid] == target,那么我们就找到了目标值,直接返回 mid 即可。
    • 如果 nums[mid] < target,这说明目标值在中间元素的右侧,我们就将左边界 left 更新为 mid + 1,继续在右侧区间进行查找。
    • 如果 nums[mid] > target,这说明目标值在中间元素的左侧,我们就将右边界 right 更新为 mid - 1,继续在左侧区间进行查找。
  4. 不断重复上述步骤,直到左边界 left 大于右边界 right,这时候就说明目标值不存在于数组中,我们返回 -1。

三、代码实现

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;while(left<=right){int mid = (left+right)/2;if(nums[mid]==target){//相等 找到啦return mid;}else if(nums[mid]<target){left = mid+1;}else{//目标值小right = mid-1;}}//没找到return -1;}
}

相关文章:

《二分查找算法:在有序数组中搜索目标值》

目录 一、问题分析 二、二分查找算法原理 三、代码实现 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target&#xff0c;我们要写一个函数来搜索 nums 中的 target&#xff0c;如果目标值存在就返回它的下标&#xff0c;否则返回 -1。 …...

【万字总结】数据结构常考应用大题做法画法详解_树_哈希表_图_排序大总结

文章目录 1.树相关应用大题1.1 已知二叉树的中序序列和前序or中序&#xff0c;画出二叉树1.2 二叉树的遍历、树的遍历、森林的遍历总结1.3二叉树与森林之间的转换1.3.1 已知树的先序序列和中序序列&#xff0c;画出森林 1.4 二叉树的线索化1.5 二叉排序树1.5.1 二叉排序树的删除…...

Docker + Jenkins + gitee 实现CICD环境搭建

目录 前言 关于Jenkins 安装Jenkins docker中运行Jenkins注意事项 通过容器中的Jenkins&#xff0c;把服务打包到docker进行部署 启动Jenkins 创建第一个任务 前言 CI/CD&#xff08;持续集成和持续交付/持续部署&#xff09;&#xff0c;它可以实现自动化的构建、测试和部署…...

rabbitMq怎么保证消息不丢失?消费者没有接收到消息怎么处理

在使用RabbitMQ时&#xff0c;保证消息不丢失以及处理消费者未接收到消息的情况可以通过以下几个方法&#xff1a; 1. 确保消息的持久化 队列持久化&#xff1a;在声明队列时将其设置为持久化&#xff08;durabletrue&#xff09;&#xff0c;这样RabbitMQ在重启后也会保留队…...

商务数据分析在提升客户体验方面的作用体现在哪些环节

在当今竞争激烈的商业环境中&#xff0c;客户体验已成为企业成功的关键因素。商务数据分析犹如一把神奇的钥匙&#xff0c;在提升客户体验的征程中发挥着至关重要的作用&#xff0c;贯穿于多个环节。 一、客户需求分析&#xff1a;洞察客户内心的窗口 客户需求分析是商务数据…...

cooladmin使用整理

1、后端关键字自动生成没有代码段提示&#xff0c;原因是拉取的项目代码中没有.vscode文件夹&#xff0c;复制一套至项目src同级即可 2、前端快速创建&#xff0c;在Entity完成后就去快速创建中选数据结构&#xff0c;这时没有对应的内容&#xff0c;数据结构是和controller层a…...

CentOS 7 更换软件仓库

CentOS 7 于2024年6月30日停止维护&#xff0c;官方仓库已经没有软件了&#xff0c;想要继续使用 &#xff0c;需要更换软件仓库&#xff0c;这里更换到阿里云的软件仓库 https://developer.aliyun.com/mirror/ 查看目前可用的软件数量 yum repolist 更换软件仓库&#xff1a…...

现代Web开发:React Hooks深入解析

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 现代Web开发&#xff1a;React Hooks深入解析 现代Web开发&#xff1a;React Hooks深入解析 现代Web开发&#xff1a;React Hook…...

HarmonyOS使用arkTS拉起指定第三方应用程序

HarmonyOS使用arkTS拉起指定第三方应用程序 前言代码及说明bundleName获取abilityName获取 前言 本篇只说采用startAbility方式拉起第三方应用&#xff0c;需要用到两个必备的参数bundleName&#xff0c;abilityName&#xff0c;本篇就介绍如何获取参数… 代码及说明 bundle…...

flex安装学习笔记

https://zhuanlan.zhihu.com/p/2783726096 3.下载 Flux 模型 FLUX.1 [dev] &#xff1a;官方版本满配版&#xff0c;最低显存要求 24G&#xff1b;FLUX.1 [dev] fp8&#xff1a;大佬优化 [dev] 后版本&#xff0c;建议选择此版本&#xff0c;最低 12G 显存可跑&#xff1b;FLU…...

09-结构化搜索、搜索的相关性算分

term 查询执行精确值匹配&#xff0c;要求文档中的字段值与指定的词项完全相等。对于日期字段等精确值字段&#xff0c;通常使用 term 查询可以快速有效地匹配文档。match 查询执行全文搜索&#xff0c;会对输入的文本进行分析&#xff0c;生成查询词项&#xff0c;并试图找到与…...

手机屏幕上进行OCR识别方案

在手机屏幕上进行OCR识别&#xff0c;可以通过一些主流方案实现高效、准确的文本识别。以下是几种常见方案&#xff1a; 1. 使用 Tesseract OCR 原理&#xff1a;Tesseract 是一个开源的 OCR 引擎&#xff0c;支持多种语言。可以通过一些优化提升其对手机屏幕文本的识别效果。…...

遗传算法与深度学习实战(22)——使用Numpy构建神经网络

遗传算法与深度学习实战&#xff08;22&#xff09;——使用Numpy构建神经网络 0. 前言1. 神经网络基础1.1 简单神经网络的架构1.2 神经网络的训练 2. 使用 Numpy 构建神经网络2.1 网络架构2.2 实现神经网络 小结系列链接 0. 前言 我们已经学习了如何使用进化算法来优化深度学…...

react->Antd->Table调整checkbox默认样式

checkbox默认不展示&#xff0c;hover此行时&#xff0c;出现checkbox,选中后不消失&#xff1a; hover前&#xff0c;设置透明边框&#xff1b; hover时&#xff0c;checkbox出现 选中后 代码块&#xff1a; .ant-checkbox {.ant-checkbox-inner {border: transparent;}}.ant…...

一种ESB的设计

系统架构 ESB包括&#xff1a; ESB总控服务、业务应用集群、业务消息WEB服务、业务消息日志服务、运维管理平台、业务设计器。如下图所示 ESB总控服务 ESB总控服务承载了各项业务的运维和管理。主要包括&#xff1a; 业务流程的管理ESB内部不同模块间的通讯ESB系统设置和管理…...

上位机常用通信方式

1. 串口通信&#xff1a;RS232&#xff08;设备和PC之间&#xff0c;最常用&#xff0c;短距离&#xff09;、RS485&#xff08;工业现场总线&#xff0c;长距离&#xff0c;多点通信&#xff09; 2. 以太网通信&#xff1a;TCP/IP协议 3. CAN总线通信 4. Modbus协议&#xff1…...

Vue3中使用LogicFlow实现简单流程图

实现结果 实现功能&#xff1a; 拖拽创建节点自定义节点/边自定义快捷键人员选择弹窗右侧动态配置组件配置项获取/回显必填项验证 自定义节点与拖拽创建节点 拖拽节点面板node-panel.vue <template><div class"node-panel"><divv-for"(item, k…...

《重学Java设计模式》之 工厂方法模式

《重学Java设计模式》之 建造者模式 《重学Java设计模式》之 原型模式 《重学Java设计模式》之 单例模式 模拟发奖多种商品 工程结构 奖品发放接口 package com.yys.mes.design.factory.store;public interface ICommodity {/*** Author Sherry* Date 14:20 2024/11/6**/voi…...

【大数据学习 | kafka】kafka的数据存储结构

以上是kafka的数据的存储方式。 这些数据可以在服务器集群上对应的文件夹中查看到。 [hexuanhadoop106 __consumer_offsets-0]$ ll 总用量 8 -rw-rw-r--. 1 hexuan hexuan 10485760 10月 28 22:21 00000000000000000000.index -rw-rw-r--. 1 hexuan hexuan 0 10月 28 …...

知识竞赛答题系统,线上答题小程序链接怎么做?

随着智能手机的普及&#xff0c;越来越多的单位开始在线上开展知识竞赛。这种形式的知识竞赛不仅易于操作&#xff0c;而且参与度更高。那么线上知识竞赛答题系统怎么做呢&#xff1f;自己可以做吗&#xff1f;答案是可以的&#xff01;借助微信答题系统制作平台风传吧&#xf…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...