二分查找法的细节

embedded/2024/10/17 12:32:06/

第一个,最基本的二分查找算法

1 因为我们初始化 right = nums.length - 1
2 所以决定了我们的「搜索区间」是 [left, right]
3 所以决定了 while (left <= right)
4 同时也决定了 left = mid+1 和 right = mid-1
5
6 因为我们只需找到一个 target 的索引即可
7 所以当 nums[mid] == target 时可以立即返回

第二个,寻找左侧边界的二分查找:

1 因为我们初始化 right = nums.length
2 所以决定了我们的「搜索区间」是 [left, right)
3 所以决定了 while (left < right)
4 同时也决定了 left = mid + 1 和 right = mid
5
6 因为我们需找到 target 的最左侧索引
7 所以当 nums[mid] == target 时不要立即返回
8 而要收紧右侧边界以锁定左侧边界

第三个,寻找右侧边界的二分查找:

1 因为我们初始化 right = nums.length
2 所以决定了我们的「搜索区间」是 [left, right)
3 所以决定了 while (left < right)
4 同时也决定了 left = mid + 1 和 right = mid
5
6 因为我们需找到 target 的最右侧索引
7 所以当 nums[mid] == target 时不要立即返回
8 而要收紧左侧边界以锁定右侧边界
9
10 又因为收紧左侧边界时必须 left = mid + 1
11 所以最后无论返回 left 还是 right,必须减一


http://www.ppmy.cn/embedded/128164.html

相关文章

Js面向对象

程序就是对现实世界的抽象,一个事物抽象到程序中后就变成了对象,在程序的世界中&#xff0c;一切皆对象 面向对象的编程指&#xff0c;程序中的所有操作都是通过对象来完成 做任何事情之前都需要先找到它的对象&#xff0c;然后通过对象来完成各种操作 一个事物通常由两部分组成…

使用Python解决化学问题的实用指南

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

数据挖掘示例分析

我们想尽量提高利润&#xff0c;为此必须确保橡皮鸭和橡皮鱼的产量都正合适。我们需要您帮忙找出理想的产品组合&#xff1a;这两种产品我们各应该生产多少&#xff1f; 一、市场需求分析 1. 调研市场对橡皮鸭和橡皮鱼的需求情况。了解当前市场上这两种产品的销售量、销售趋势…

基于Matlab使用蚁群算法寻找最优路径

基于Matlab使用蚁群算法寻找最优路径 与Dijkstra算法使用相同的地图。 每只蚂蚁都从起点出发&#xff0c;直到抵达终点。这与Example5_1.m 中解决旅行商问题不一样&#xff0c;旅行商问题中每一代的蚂蚁都是随机从一个节点出发。 文件说明 Example5_1.m 简单对参考资料2中的…

STM32 DMA控制器

目录 STM32 DMA的基本概念 DMA的定义 DMA传输的基本要素 DMA传输过程 DMA的优点与应用 STM32 DMA的结构和主要特征 DMA处理 DMA通道 DMA 中断 DMA的HAL驱动函数 STM32 DMA的基本概念 在很多的实际应用中&#xff0c;有进行大量数据传输的需求&#xff0c;这时如果CP…

UE5 猎户座漂浮小岛 03 视觉效果 粒子

UE5 猎户座漂浮小岛 03 视觉效果 粒子 1.视觉效果 1.1 指数级高度雾 fog指数高度雾组件 0.1、1.4 内颜-淡蓝体雾 1.2 体积光 太阳 directionallight-强度光强-3颜色-淡蓝光束-遮 遮暗-0.018范-10000 1.3 天光 天空照亮&#xff0c;泛光&#xff0c;照大地 skylight强范…

Javascript——html生成并预览 PDF及html导出为Word

html生成并预览 PDF <template><div><div ref"content"><!-- 这里放置你想要转换为 PDF 的 HTML 内容 --><h1>标题</h1><p>这是一些内容。</p></div><button click"exportToPDF">生成并预览 …

R语言绘制聚类热图

聚类热图是一种直观的数据可视化工具。它以矩形彩色图表的形式呈现数据矩阵&#xff0c;每个单元格颜色对应特定数值&#xff0c;通常从低值的冷色调到高值的暖色调渐变。常应用于多个领域&#xff0c;如生物学中分析基因表达、蛋白质相互作用和生物群落&#xff1b;金融领域用…