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

数据结构与算法之二分查找分而治之思想


决定我们成为什么样人的,不是我们的能力,而是我们的选择。——《哈利·波特与密室》


二分查找是查找算法里面是很优秀的一个算法,特别是在有序的数组中,这种算法思想体现的淋漓尽致。

一.题目描述及其要求

请实现无重复数字的升序数组的二分查找:

给定一个 元素升序的、无重复数字的整型数组 arr和一个目标值 target ,写一个函数搜索 arr中的 target,如果目标值存在返回下标(下标从 0 开始),否则返回 -1.

示例一:

输入:[-1,0,3,4,6,10,13,14],13
返回值:6
说明:13 出现在arr中并且下标为 6 

示例二:

输入:[],3
返回值:-1
说明:arr为空,返回-1  

示例三:

输入:[-1,0,3,4,6,10,13,14],2
返回值:-1
说明:2 不存在arr中因此返回 -1 

二.分治思想

分治即“分而治之”,“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题子问题继续按照这样划分直到问题可以被轻易解决“治”指的是将子问题单独进行处理。经过分治后的子问题,需要将解进行合并才能得到原问题的解,因此整个分治过程经常用递归来实现。

1.逐个遍历思路:

本来我们可以遍历数组直接查找,每次检查当前元素是不是要找的值。

for(int i = 0; i <length; i++)if(arr[i] == target)return i;

2.逐个遍历出现的问题

但是这样这个有序的数组我们就没有完全利用起来。

我们想想,若是目标值比较小,肯定在前半区间,若是目标值比较大,肯定在后半区间,怎么评价大小?我们可以用中点值作为一个标杆,将整个数组分为两个区间,目标值与中点值比较就能知道它会在哪个区间,这就是分治的思维。

三分治思想具体做法:

  • step 1:从数组首尾开始,每次取中点值。

  • step 2:如果中间值等于目标即找到了,可返回下标,如果中点值大于目标,说明中点以后的都大于目标,因此目标在中点左半区间,如果中点值小于目标,则相反。

  • step 3:根据比较进入对应的区间,直到区间左右端相遇,意味着没有找到

代码实现:

int search(int*arr, int length, int target ) {if(length == 0) return -1;int left=0, right=length-1;while(left<=right) {int mid = left+(right-left)/2;if(arr[mid]==target) return mid;if(arr[mid]<target) left=mid+1;if(arr[mid]>target) right=mid-1;}return -1;
}

ps:int mid = left+(right-left)/2;与int mid=(left+right)/2是一样的,但是选择前者更安全,因为后者两个整数相加数据过于庞大可能会出现数据溢出的情况,所以采用前者更加可靠。

也可以这样写:mid = left+(right-left >> 1); +-大于位移运算的优先级 左移*2

本算法到这,其实二分查找可以分为几种情况来讨论,这里提供一种比较好理解的方案,具体算法大家可以参考相应资料自了解,大家加油。。。。。最近在做算法题目可以关注我,点个赞,有问题可以一起讨论。以后的几篇文章都讲解算法的题目。

相关文章:

数据结构与算法之二分查找分而治之思想

决定我们成为什么样人的&#xff0c;不是我们的能力&#xff0c;而是我们的选择。——《哈利波特与密室》二分查找是查找算法里面是很优秀的一个算法&#xff0c;特别是在有序的数组中&#xff0c;这种算法思想体现的淋漓尽致。一.题目描述及其要求请实现无重复数字的升序数组的…...

训练自己的中文word2vec(词向量)--skip-gram方法

训练自己的中文word2vec&#xff08;词向量&#xff09;–skip-gram方法 什么是词向量 ​ 将单词映射/嵌入&#xff08;Embedding&#xff09;到一个新的空间&#xff0c;形成词向量&#xff0c;以此来表示词的语义信息&#xff0c;在这个新的空间中&#xff0c;语义相同的单…...

ubuntu系统环境配置和常用软件安装

系统环境 修改文件夹名称为英文 参考链接 export LANGen_US xdg-user-dirs-gtk-update 常用软件安装 常用工具 ping 和ifconfig工具 sudo apt install -y net-tools inetutils-ping 截图软件 sudo apt install -y net-tools inetutils-ping flameshot 录屏 sudo apt-get i…...

【1139. 最大的以 1 为边界的正方形】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个由若干 0 和 1 组成的二维网格 grid&#xff0c;请你找出边界全部由 1 组成的最大 正方形 子网格&#xff0c;并返回该子网格中的元素数量。如果不存在&#xff0c;则返回 0。 示例 1&#…...

windows11安装sqlserver2022报错

window11安装SQL Server 2022 报错 糟糕… 无法安装SQL Server (setup.exe)。此 SQL Server安装程序介质不支持此OS的语言&#xff0c;或没有SQL Server英语版本的安装文件。请使用匹配的特定语言SQL Server介质;或安装两个特定语言MUI&#xff0c;然后通过控制面板的区域设置…...

Python快速上手系列--日志模块--详解篇

前言本篇主要说说日志模块&#xff0c;在写自动化测试框架的时候我们就需要用到这个模块了&#xff0c;方便我们快速的定位错误&#xff0c;了解软件的运行情况&#xff0c;更加顺畅的调试程序。为什么要用到日志模块&#xff0c;直接print不就好了&#xff01;那得写多少print…...

【THREE.JS学习(1)】绘制一个可以旋转、放缩的立方体

学习新技能&#xff0c;做一下笔记。在使用ThreeJS的时候&#xff0c;首先创建一个场景const scene new THREE.Scene();接着&#xff0c;创建一个相机其中&#xff0c;THREE.PerspectiveCamera&#xff08;&#xff09;四个参数分别为&#xff1a;1.fov 相机视锥体竖直方向视野…...

数仓实战 - 滴滴出行

项目大致流程&#xff1a; 1、项目业务背景 1.1 目的 本案例将某出行打车的日志数据来进行数据分析&#xff0c;例如&#xff1a;我们需要统计某一天订单量是多少、预约订单与非预约订单的占比是多少、不同时段订单占比等 数据海量 – 大数据 hive比MySQL慢很多 1.2 项目架…...

python虚拟环境与环境变量

一、环境变量 1.环境变量 在命令行下&#xff0c;使用可执行文件&#xff0c;需要来到可执行文件的路径下执行 如果在任意路径下执行可执行文件&#xff0c;能够有响应&#xff0c;就需要在环境变量配置 2.设置环境变量 用户变量&#xff1a;当前用户登录到系统&#xff0c;…...

BeautifulSoup文档4-详细方法 | 用什么方法对文档树进行搜索?

4-详细方法 | 用什么方法对文档树进行搜索&#xff1f;1 过滤器1.1 字符串1.2 正则表达式1.3 列表1.4 True1.5 可以自定义方法2 find_all()2.1 参数原型2.2 name参数2.3 keyword 参数2.4 string 参数2.5 limit 参数2.6 recursive 参数3 find()4 find_parents()和find_parent()5…...

初识Tkinter界面设计

目录 前言 一、初识Tkinter 二、Label控件 三、Button控件 四、Entry控件 前言 本文简单介绍如何使用Python创建一个界面。 一、初识Tk...

软件测试面试题中的sql题目你会做吗?

目录 1.学生表 2.一道SQL语句面试题&#xff0c;关于group by表内容&#xff1a; 3.表中有A B C三列,用SQL语句实现&#xff1a;当A列大于B列时选择A列否则选择B列&#xff0c;当B列大于C列时选择B列否则选择C列 4. 5.姓名&#xff1a;name 课程&#xff1a;subject 分数&…...

VS实用调试技巧

一.什么是BUG&#x1f41b;Bug一词的原意是虫子&#xff0c;而在电脑系统或程序中隐藏着的一些未被发现的缺陷或问题&#xff0c;人们也叫它"bug"。这是为什么呢&#xff1f;这就要追溯到一个程序员与飞蛾的故事了。Bug的创始人格蕾丝赫柏&#xff08;Grace Murray H…...

通俗易懂理解三次握手、四次挥手(TCP)

文章目录1、通俗语言理解1.1 三次握手1.2 四次挥手2、进一步理解三次握手和四次挥手2.1 三次握手2.2 四次挥手1、通俗语言理解 1.1 三次握手 C:客户端 S&#xff1a;服务器端 第一次握手&#xff1a; C&#xff1a;在吗&#xff1f;我要和你建立连接。 第二次握手&#xff…...

1.1 什么是并发

1.1 什么是并发 并发&#xff1a;指两个或更多独立的活动同时发生。并发在生活中随处可见。我们可以一边走路一边说话&#xff0c;也可以两只手同时做不同的动作。 1.1.1 计算机系统中的并发 当我们提到计算机术语的“并发”&#xff0c;指的是在单个系统里同时执行多个独立…...

万字讲解你写的代码是如何跑起来的?

今天我们来思考一个简单的问题&#xff0c;一个程序是如何在 Linux 上执行起来的&#xff1f; 我们就拿全宇宙最简单的 Hello World 程序来举例。 #include <stdio.h> int main() {printf("Hello, World!\n");return 0; } 我们在写完代码后&#xff0c;进行…...

034.Solidity入门——21不可变量

Solidity 中的不可变量是在编译时就被确定的常量&#xff0c;也称为常量变量&#xff08;constant variable&#xff09;或只读变量&#xff08;read-only variable&#xff09;。这些变量在定义时必须立即初始化&#xff0c;并且在整个合约中都无法被修改&#xff0c;可以在函…...

Vulnhub 渗透练习(四)—— Acid

环境搭建 环境下载 kail 和 靶机网络适配调成 Nat 模式&#xff0c;实在不行直接把网络适配还原默认值&#xff0c;再重试。 信息收集 主机扫描 没扫到&#xff0c;那可能端口很靠后&#xff0c;把所有端口全扫一遍。 发现 33447 端口。 扫描目录&#xff0c;没什么有用的…...

C++ 在线工具

online编译器https://godbolt.org/Online C Compiler - online editor (onlinegdb.com) https://www.onlinegdb.com/online_c_compilerC Shell (cpp.sh) https://cpp.sh/在线文档Open Standards (open-std.org)Index of /afs/cs.cmu.edu/academic/class/15211/spring.96/wwwC P…...

使用MMDetection进行目标检测、实例和全景分割

MMDetection 是一个基于 PyTorch 的目标检测开源工具箱&#xff0c;它是 OpenMMLab 项目的一部分。包含以下主要特性&#xff1a; 支持三个任务 目标检测&#xff08;Object Detection&#xff09;是指分类并定位图片中物体的任务实例分割&#xff08;Instance Segmentation&a…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

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

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

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...