【算法集训】基础算法:二分查找 | 概念篇

二分枚举,也叫二分查找,指的就是给定一个区间,每次选择区间的中点,并且判断区间中点是否满足某个条件,从而选择左区间继续求解还是右区间继续求解,直到区间长度不能再切分为止。
由于每次都是把区间折半,又叫折半查找,时间复杂度为 O(logn),和线性枚举的求解结果一直,但是高效许多,返回值可以是下标,也可以是元素本身。

【例题3】只有两种颜色的数组 arr ,左边部分为红色用 0 表示,右边部分为绿色用 1 表示,要求找到下标最小的绿色元素的下标。


如图所示,下标最小的绿色元素的下标为 3,所以应该返回 3。

算法分析

1)目标

对于这个问题,当我们拿到这个数组的时候,第一个绿色位置在哪里,我们是不知道的,所以,现在的目标就是要通过二分枚举找到红色区域和绿色区域的边界。

2)游标

利用线性枚举的思路,我们引入游标的概念,只不过需要两个游标,左边一个红色游标,右边一个绿色游标。并且游标初始位置都在数组以外,对于一个 n 个元素的数组,红色游标初始位置在 -1,绿色游标初始位置在 n。

3)二分

我们将两个游标相加,并且除 2,从而得到游标的中点,并且判断中点所在位置的颜色,发现是绿色的,这说明从 中点游标 到 绿色游标 的元素都是绿色的。如下图所示:

于是,我们可以把 绿色游标 替换成 中点游标,如下图所示:

这样就完成了一次二分,区间相比之前,缩小了一半。注意,我们要求的解,一定永远在 红色游标 和 绿色游标 之间。
然后,我们继续将两个游标相加,并且除 2,从而得到游标的中点,并且判断中点所在位置的颜色,发现是红色的,这说明从 红色游标 到 中点游标 的元素都是红色的。如下图所示:

于是,我们可以把 红色游标 替换成 中点游标 ,如下图所示:

同样上述算法,再经过两次二分以后,我们得到了如下结果:

这个时候,这个时候 红色游标 和 绿色游标 的位置一定相差 1,并且 绿色游标 的位置就是我们这个问题要求的解。

二分查找模版

int binarySearch(int *arr, int arrSize, int x) {
    int l = -1, r = arrSize; // (1)
    int mid;
    while(r - l > 1) { // (2
        mid = l + (r - l) / 2; // (3)
        if( isGreen(arr[mid], x) ) {
            r = mid; // (5)
        }else {
             l = mid; // (6)
        }
    }
    return r; // (7)
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520454.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AUTOSAR MCAL for SemiDrive E3 功能模块使用介绍:I2C

一、 概述 本文主要介绍如何使用芯驰提供的 AUTOSAR MCAL 软件包,开发 SemiDrive E3 的 I2C 模块,对 RTC 芯片进行读写操作。 硬件使用 E3640 GATEWAY 开发板,软件包为 mcal3.1。 图1 硬件环境 二、模块简介 E3 系列最多支持 8 个 I2C&am…

【51单片机入门记录】A/D D/A转换器概述

目录 一、A/D D/A转换器简介 (1)模数转换器-ADC (analogue-to-digital conversion) (2)数模转换器-DAC(digital-to-analogue conversion) (3)应用场景 二…

全国计算机等级考试三级Linux应用与开发技术考试-习题汇总

https://blog.csdn.net/qq_42025798/article/details/119155696 3.第1章-计算机体系结构与操作系统-练习题-简答题 https://blog.csdn.net/qq_42025798/article/details/119186151 4.第1章-计算机体系结构与操作系统-练习题-填空题 https://blog.csdn.net/qq_42025798/article/…

gulp项目配置,压缩css,压缩js,进行监听文件改动

1,创建项目 npm install -g gulp这个应该很熟悉,就是全局安装gulp 2,创建一个工程,使用node创建,统一命令 npm init -y3,创建后,目录出现一个package.json文件,没错,就是我们用vu…

【Leetcode每日一题】模拟 - 外观数列(难度⭐⭐)(51)

1. 题目解析 题目链接:38. 外观数列 这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。 2.算法原理 所谓“外观数列”,其实只是依次统计字符串中连续且相同的字符的个数。依照题意,依次模拟即 可。…

Java面向对象进阶基础知识

面向对象进阶 static 静态变量 被该类的所有的对象共享 不属于对象,属于类 随着类的加载而加载,优先于对象存在 类名调用(推荐) 对象名调用 static的注意事项 静态方法中没有this关键字 静态方法,只能访问静态 非静态方法可以访问所有 在Java中,static关…

元宇宙虚拟空间的碰撞体检测(四)

前言 该文章主要讲元宇宙虚拟空间的碰撞体检测,基本技术点,不多说,直接引入正题。 碰撞体检测 这里可以看到检测代码的逻辑是经过一系列判断,最后判断模型类型属性如果是trimesh,那么通过解析出来的顶点来生成我们的…

Linux:IO多路转接之select

文章目录 selecttimeval结构体fd_set 优缺点分析完整代码 本节要介绍的主题是多路转接式IO select 先说结论,这个select是做什么的呢? select是负责在Linux系统中,让一个人可以有多个鱼竿,可以不停的进行轮询,只要有…

【C语言基础】:文件操作详解(前篇:准备知识)

文章目录 一、什么是文件以及文件的分类1.1 程序文件1.2 数据文件1.3 文件名 二、文本文件和二进制文件2.1 数据在文件中的存储 三、文件的打开和关闭3.1 流和标准流3.1.1 流3.1.2 标准流 3.3 文件指针3.5 文件的打开和关闭 一、什么是文件以及文件的分类 文件是指存储在计算机…

【SCI绘图】【曲线图系列1 python】绘制扫描点平滑曲线图

SCI,CCF,EI及核心期刊绘图宝典,爆款持续更新,助力科研! 本期分享: 【SCI绘图】【曲线图1 python】绘制扫描点平滑曲线图 1.环境准备 python 3 import numpy as np import pandas as pd import proplot …

代码随想第31天 | 122.买卖股票的最佳时机II 、 55. 跳跃游戏 、 45.跳跃游戏II

一、前言 参考文献:代码随想录 今天主要还是贪心,但是是比较难想到的题目,不管那么多吧,直接做吧! 二、买卖股票的最佳时机|| 1、思路: 这个思路我确实想不出来,但是这个思路又异常的简单&…

MySQL复制拓扑1

文章目录 主要内容一.安装MySQL服务器1.MySQL 安装程序和其它文件保存在下发的 mysql8-files.iso 镜像文件中,可以使用虚拟光驱来提取到 Linux 文件系统。代码如下(示例): 2.将 MySQL8.0 程序解压到 /opt 目录,再创建到 MySQL 默认…

c# wpf LiveCharts 绑定 简单试验

1.概要 c# wpf LiveCharts 绑定 简单试验 2.代码 <Window x:Class"WpfApp3.Window2"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…

嵌入式驱动学习第六周——内核函数调用(堆栈打印)

前言 在内核中&#xff0c;函数调用堆栈非常重要&#xff0c;因为它可以帮助开发人员理解代码是如何执行的&#xff0c;从而进行调试、性能优化或问题排查。堆栈可以显示当前执行的函数以及导致该函数调用的先前函数&#xff0c;从而形成一个函数调用链。本篇博客就介绍堆栈打印…

编程新手必看,学习python中字符串数据类型内容(8)

1、 Python3 字符串 字符串是 Python 中最常用的数据类型。我们可以使用引号( ’ 或 " )来创建字符串。 创建字符串很简单&#xff0c;只要为变量分配一个值即可。例如&#xff1a; var1 Hello World! var2 "Runoob"Python 访问字符串中的值 Python 不支持单…

虚拟主机、VPS主机和云服务器的区别

对于每个建站新手来说&#xff0c;首先要解决的就是服务器购买的问题&#xff0c;目前市面有很多类型的服务器&#xff0c;常见的有&#xff1a;阿里云、腾讯云、Vultr云服务器&#xff0c;也有RackNerd、Cloudways等提供的VPS&#xff0c;还有SiteGround、ChemiCloud 、 Hosti…

如何保护大模型API安全

大模型的崛起正在改变着我们对机器学习和人工智能的理解&#xff0c;它们不仅提供了令人惊叹的预测和分析能力&#xff0c;还在各行各业的应用中发挥着重要作用。通过提供 API&#xff0c;用户无需了解底层实现细节&#xff0c;使大型模型能够更好地与用户和应用程序进行交互&a…

C++面向对象程序设计 - 对象指针和this指针

在C学习中&#xff0c;指针是一个用于指向另一个变量的地址的变量。理解指针有一定难度&#xff0c;但是理解它的工作原理后&#xff0c;会发现它们是非常强大和有用的工具。指针可以用来指向一般的变量&#xff0c;也可以指向对象。 一、指向对象的指针 在建立对象时&#xf…

C++——栈和队列容器

前言&#xff1a;这篇文章我们将栈和队列两个容器放在一起进行分享&#xff0c;因为这两个要分享的知识较少&#xff0c;而且两者在结构上有很多相似之处&#xff0c;比如栈只能在栈顶操作&#xff0c;队列只能在队头和队尾操作。 不同于前边所分享的三种容器&#xff0c;这篇…