二分查找的讲义和视频

这篇具有很好参考价值的文章主要介绍了二分查找的讲义和视频。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 

源码下载:

https://pan.baidu.com/s/1wMsUK4hZpdttFzOK66n3mQ?pwd=x7a7 提取码 x7a7

先进入《 视频教程及配套源码》,再进入《C++算法》。

在线看视频:

https://www.bilibili.com/video/BV1nL411Q7DY/ 

 

1.1. 基础

1.1.1. 最简单的情况

a. 情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数,返回任意一个。

b. 原理

如果中间数和目标数相等,返回中间数索引。

如果中间数小于目标数,则目标数一定不在前半部分。

如果中间数大于目标数,则目标数一定不在后半部分。

假定数组区域是左闭右开区间,中间索引=(左索引+右索引)/2

c. 测试数据

04中找1

轮次

待查数据

中间数

第一轮

0 1 2 3 4

2

第二轮

0 1

1

 

15中查找4

轮次

待查数据

中间数

第一轮

1 2 3 4 5

3

第二轮

4 5

5

第三轮

4

4

 

1.1.2. 重复数据返回第一个

a. 情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数,返回第一个。

b. 原理

如果中间数小于目标数,则目标数一定不在前半部分。

如果中间数大于目标数,则目标数一定不在后半部分。

如果中间数等于目标数,则目标数一定不在后半部分。由于左半部分必须包括中间数,所以左开右闭区间。

c. 测试数据

1,2中寻找2

轮次

待查数据

索引

中间数

第一轮

1 2

(-1,1]

1

第二轮

2

(0,1]

2

 

2,2,3中寻找2

 

轮次

待查数据

索引

中间数

第一轮

2 2 3

(-1,2]

2

第二轮

2 2

(-1,1]

2

第三轮

2

(-1,0]

2

 

2,3,4中寻找2

轮次

待查数据

索引

中间数

第一轮

2 3 4

(-1,2]

3

第二轮

2 3

(-1,1]

2

第三轮

2

(-1,0]

2

1.1.3. 重复数据返回最后一个

a. 情况简述

数组已经按升序排好序。

假定要找的数一定存在。

如果存在重复的数,返回最后一个。

b. 原理

一,如果中间数小于目标数,则目标数一定不在左边、中间,可能在右边。

二,如果中间数大于目标数,则目标数一定不在右边、中间,可能在左边。

三,如果中间数等于目标数,则目标数一定不在左边,可能在中间、右边。

数据

左闭右开

0,1,2,3

0,1

2((0+4)/2)

3

0,1,2

0

1

2

0,1

0

1

 

左开右闭

0,1,2,3

0

1(-1+3)/2

2,3

0,1,2

 

0

1,2

0,1

 

0

1

结论:右(左)开,中间数就和右(左)区间合并,可以保持数据量均衡,左右数量相差不超过1。结合原理三,用左闭右开区间。

 

使用左闭右开(中右合并)后,情况分类

中间数<目标数

中右

>

=

中右

结论:小于等于可以合并

c. 测试数据

 

寻找

期望值

0123

0

0

0123

1

1

0123

2

2

1123

1

1

0113

1

2

 

 

 

 

1.1.4. 循环代替递归

循环结束的条件:元素数量小于2。计算的元素数量可能是0,也可能是负数(非法数据)。由于是二分,所以左右边界一个不变, 一个变成中间位置。

1.1.5. 目标数不一定存在

a. 如果目标数不存在,返回-1

解决方法:返回前,判断是否等于目标值,如果不是返回-1

b. 如果目标数不存在,返回它应该插入的位置

左开右闭

 

数据(寻找0

左右中间索引

1,3,5,7

0,4,2

1,3

0,2,1

1

0,1,0结束

数据(寻找2

左右中间索引

1,3,5,7

0,4,2

1,3

0,2,1

1

0,1结束

数据(寻找4

左右中间索引

1,3,5,7

0,4,2

1,3

0,2,1

3

1,2,1结束

数据(寻找6

左右中间索引

1,3,5,7

0,4,2

5,7

2,4,3

5

2,3,2结束

数据(寻找8

左右中间索引

1,3,5,7

0,4,2

5,7

2,4,3

7

3,4,3结束

规律:

if (vec[left] < iTarget)

{

return left+1;

}

1.1.6. stl二分函数

a. 小于、等于、大于iNum的数

const int iNum = 3;

auto it1 = data.lower_bound(iNum);

auto it2 = data.upper_bound(iNum);

[data.begin(),it1) 表示小于iNum的数。

[it1,it2)表示等于iNum的数。

[it2,data.end()) 表示大于iNum的数。

b. 大于、等于iNum1小于等于iNum2的数

const int iNum1 = 3,iNum2=7;

auto it1 = data.lower_bound(iNum1);

auto it2 = data.upper_bound(iNum2);

视频顺便演示了大于iNum1小于iNum2

c. 对向量二分

const int iNum1 = 3,iNum2=7;

std::sort(data.begin(), data.end());

auto it1 = std::upper_bound(data.begin(), data.end(),iNum1);

auto it2 = std::lower_bound(data.begin(), data.end(), iNum2);

d. 降序

见视频。

e. 通过vector<int>v[1]查找

std::sort(data.begin(), data.end(), [](const std::vector<int>& v1, const std::vector<int>& v2)

{return v1[1] < v2[1]; });

auto it1 = std::lower_bound(data.begin(), data.end(), iNum1, [](const std::vector<int>& v1, int iNum)

{

return v1[1] < iNum;

});

auto it2 = std::upper_bound(data.begin(), data.end(), iNum1, [](int iNum, const std::vector<int>& v2)

{return iNum < v2[1]; });

1.2. 习题

1.2.1. 最大亲密度

有若干包饼干,每包饼干的数量记录在数组nums中,比如:{4,175} ,分配给若干(如:3)小朋友。

每种分配方案的亲密度:任意两个小朋友饼干数的差的绝对值的最小值。

求所有分配方案中的最大亲密度。

分配方案{1,7,5}的亲密度=min(7-1,5-1,7-5}=2

分配方案{4,7,5}的亲密度=min(7-4,5-4,7-5}=1

分配方案{4,1,5}的亲密度=min(4-1,5-4,5-1}=1

分配方案{4,1,7}的亲密度=min(4-1,7-4,7-1)=3

1. 解决思路

先按升序排序。

完成函数is,判断是否存在方案能够满足亲密只大于等于iQinMi

 

因为要找最大值,所以中值符合的时候,抛弃左边。中值跟随右边,用左开右闭。文章来源地址https://www.toymoban.com/news/detail-510246.html

到了这里,关于二分查找的讲义和视频的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • uniapp - 【全端兼容】实现保存视频到手机相册功能,将 mp4 在线视频下载并存储到用户的手机中,uniapp App h5 小程序将视频文件下载保存(详细示例源码及注释一键复制,开箱即用!)

    在uniapp开发中,实现安卓苹果app、h5网页网站、小程序保存视频到相册功能,点击保存按钮后下载视频并将其存储到用户的手机相册中,完整示例源码及注释,新手小白开箱即用! 直接复制代码,稍微改下就能用到你的项目中去了(保证可用)。 可复制运行,或按需复制。

    2024年02月09日
    浏览(183)
  • 浏览器网页内嵌Qt-C++音视频播放器的实现,支持软硬解码,支持音频,支持录像截图,支持多路播放等,提供源码工程下载

        在浏览器中实现播放RTSP实时视频流,⼤体上有如下⼏个⽅案: ⽅案一:浏览器插件⽅案 ActiveX、NPAPI、PPAPI     ActiveX插件适用于IE浏览器,NPAPI与PPAPI插件适用于谷歌浏览器,不过这些插件都已经不被浏览器所支持。 ⽅案二:先转码再转流⽅案     ⼯作原理是架设一

    2024年01月17日
    浏览(97)
  • git下载源码及环境搭建下载源码之后端(一)

    下载源码 使用 windows + R 使用cmd调用命令框下载gitee云上面的 源码文件 输入命令: Git clone (此处拼接gitee源代码 地址) 若使用 git 命令 clone 项目时 我们需要在系统变量中进行配置,配置流程如下所示: 计算机—右键—属性–高级系统设置—高级–环境变量—系统变量–p

    2024年02月16日
    浏览(51)
  • Android源码下载

        最近在做Monkey二次开发的工作,边弄边在这里记录下(多平台发布),顺便可以和大家一起讨论下;  Monkey的编译依赖于Android源码,所以要修改Monkey后打新jar包,需要完整的Android源码环境。         整理了下Android源码的下载流程;         参考文档:source.downloadin

    2024年02月07日
    浏览(55)
  • Linux内核源码下载

    github:https://github.com/torvalds/linux linux源码官网:https://www.kernel.org/ linux源码官网:https://www.kernel.org/ 左侧不同分支分别对应,主线,稳定版,长期支持版 和不同的版本 选择要下载的分支,点击右侧的[browse] 然后点击上方的summary列表, 在最下侧就可以看到git下载链接 github下载

    2024年02月12日
    浏览(57)
  • 易支付源码最新版开源开发搭建附源码下载

    预计到2024年,全球电子商务销售额将达到6万亿美元,零售商将实体店转移到网上从未像现在这样容易。商家可以建立自己的网站,在网上列出他们的实体产品,完成支付并发展他们的业务,甚至不用离开沙发。现在,数字化转型已经从店面扩展到产品本身。 不管你是否意识

    2024年04月11日
    浏览(46)
  • uboot源码下载以及编译

    环境:ubuntu 20.04 uboot官网在进入之后如下所示: 我们可以直接选择Obtaining the source进入到获取源码的网址 在点击Obtaining the source进入到新的网址之后就会看到下面提示去获取uboot的源码: The source of the U-Boot project is maintained in a Git repository. You can download the source via A mirror of th

    2024年02月02日
    浏览(49)
  • scratch源码下载 | 几何冲刺

    程序说明: 《几何冲刺》是一款基于Scratch平台开发的跑酷类游戏程序。在这个游戏中,玩家控制一个黄色的小方块,在快速向前冲刺的过程中躲避各种障碍物。通过按下键盘上的上方向键,玩家可以操作小方块进行跳跃,以避开途中的障碍。游戏的目标是尽可能让黄色小方

    2024年02月19日
    浏览(69)
  • Android 源码下载(详细版)

    经典好文推荐,通过阅读本文,您将收获以下知识点: 一、下载AOSP前的准备 二、国内网络下 clone 清华大学开源软件镜像 三、编写Python脚本,开始下载android-10.0.0_r40 源码 四、源码下载工具包 五、参考文献 想在国内网络下载AOSP源码,需要电脑配置如下环境 1.安装Git 2.安装

    2024年02月12日
    浏览(43)
  • Android源码下载方法详解

            Android源码获取途径大致分为三种: 1.芯片厂商         谷歌发布新版本源码之后,芯片厂商会根据自己的芯片特性进行适配。如高通、瑞芯微等厂商。 2.方案公司         方案公司从芯片厂商获得已适配版本,并在其基础上做一些定制化的修改。 3.谷歌网站  

    2024年04月26日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包