当前位置: 首页 > 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…...

使用ThreadLocal实现当前登录信息的存取

有志者&#xff0c;事竟成 文章持续更新&#xff0c;可以关注【小奇JAVA面试】第一时间阅读&#xff0c;回复【资料】获取福利&#xff0c;回复【项目】获取项目源码&#xff0c;回复【简历模板】获取简历模板&#xff0c;回复【学习路线图】获取学习路线图。 文章目录一、使用…...

高通平台开发系列讲解(Android篇)AudioTrack音频流数据传输

文章目录 一、音频流数据传输通道创建1.1、流程描述1.2、流程图解二、音频数据传输2.1、流程描述2.2、流程图解沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇章主要图解AudioTrack音频流数据传输 。 一、音频流数据传输通道创建 1.1、流程描述 AudioTrack在set函…...

BUUCTF-firmware1

题目下载&#xff1a;下载 新题型&#xff0c;记录一下 题目给出了flag形式&#xff0c;md5{网址&#xff1a;端口}&#xff0c;下载发现是一个.bin文件 二进制文件&#xff0c;其用途依系统或应用而定。一种文件格式binary的缩写。一个后缀名为".bin"的文件&#x…...

【C++之容器篇】二叉搜索树的理论与使用

目录前言一、二叉搜索树的概念二、二叉搜素树的模拟实现&#xff08;增删查非递归实现&#xff09;1. 二叉搜素树的结点2. 二叉搜索树的实现&#xff08;1&#xff09;. 二叉搜索树的基本结构&#xff08;2&#xff09;构造函数&#xff08;3&#xff09;查找函数&#xff08;4…...

爬虫神级解析工具之XPath:用法详解及实战

一、XPATH是什么 Xpath最初被设计用来搜寻XML文档,但它同样适用于HTML文档的搜索。通过简洁明了的路径选择表达式,它提供了强大的选择功能;同时得益于其内置的丰富的函数,它可以匹配和处理字符串、数值、时间等数据格式,几乎所有节点我们都可以通过Xpath来定位。 在Pyth…...

Markdown编辑器

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…...

数据结构<堆>

&#x1f387;&#x1f387;&#x1f387;作者&#xff1a; 小鱼不会骑车 &#x1f386;&#x1f386;&#x1f386;专栏&#xff1a; 《数据结构》 &#x1f393;&#x1f393;&#x1f393;个人简介&#xff1a; 一名专科大一在读的小比特&#xff0c;努力学习编程是我唯一…...

Linux下Socket编程利用多进程实现一台服务器与多台客户端并发通信

文章目录前言一、服务器 server二、客户端 client三、并发通信演示四、程序源码前言 前些日子同“ Linux应用编程 ”专栏中发布过的TCP及UDP在Linux或Windows下的通信都为单进程下的Socket编程&#xff0c;若还存在一些套接字相关函数模糊不清&#xff0c;读者可移步“Socket编…...

【MySQL】数据库基础

目录 1、什么是数据库 2、 数据库基本操作 2.1 查看当前数据库 2.2 创建一个数据库 2.3 选中数据库 2.4 删除数据库 3、常见的数据类型 3.1 数值类型 3.2 字符串类型 3.3 日期类型 4、表的操作 4.1 创建表 4.2 查看指定数据库下的所有表 4.3 查看表的结构 4.…...

Microsoft Office 2021 / 2019 Direct Download Links

前言 微软Office在很长一段时间内都是最常用和最受欢迎的软件。从小型创业公司到大公司,它的使用比例相当。它可以很容易地从微软的官方网站下载。但是,微软只提供安装程序,而不提供完整的软件供下载。这些安装文件通常比较小。下载并运行后,安装的文件将从后端服务器安装M…...

橘子seo/沈阳网站推广优化

aidl(Android Interface Definition Language) 进程间通信需求场景:1.两个不同的应用程序之间通讯需要2.复用以前app已有的功能实现原理&#xff1a;1.IPC在这之前我们先简单说一下IPC&#xff0c;IPC是Inter-Process Communication的缩写&#xff0c;是进程间通信或者跨进程通…...

用asp做网站需要准备什么/如何让关键词排名靠前

目录 Java是什么&#xff1f; Java工作原理 目录介绍 第1章 Java面向对象 第2章 Java异常 第3章 Java数组 第4章 Java常用类 第5章 Java集合 第6章 Java IO流 第7章 Java线程 第8章 Java反射 第9章 Socket编程 第10章 Java注解开发 第11章 Java GoF设计模式 第1…...

织梦cms官方网站/小说推文推广平台

描述 编写一个程序&#xff0c;将输入字符串中的字符按如下规则排序。 规则 1 &#xff1a;英文字母从 A 到 Z 排列&#xff0c;不区分大小写。 如&#xff0c;输入&#xff1a; Type 输出&#xff1a; epTy 规则 2 &#xff1a;同一个英文字母的大小写同时存在时&#xff0…...

算命手机网站开发/seo站内优化培训

rpm命令简介&#xff1a;rpm:软件管理器数据库&#xff1a;/var/lib/rpm 用于软件进行查询相关操作的数据库。rpmbuild:用于创建rpm软件包的工具对软件进行安装、查询、卸载、升级、校验、数据库的重建、验证数据包等工作。1&#xff0e;命令格式&#xff1a;1、rpm命名规则&…...

郑州网站制作汉狮网络/宁波seo推广优化哪家强

var 、let 、const的区别 何为闭包 Promise 继承call、apply 实现深拷贝 数据类型 字符串截取正则 原形和原形链 面试30秒链接 转载于:https://juejin.im/post/5cc6d43b6fb9a031ed20c584...

公司网站用个人备案可以/谷歌官网下载

【信奥赛一本通】1208&#xff1a;2的幂次方表示1.【题目描述】2.【解题思路】3.【代码】1.【题目描述】 【题目描述】 任何一个正整数都可以用2的幂次方表示。例如&#xff1a; 137272320 同时约定方次用括号来表示&#xff0c;即ab可表示为a(b)。由此可知&#xff0c;137可…...