C++刷题 -- 二分查找

C++刷题 – 二分查找

文章目录

  • C++刷题 -- 二分查找
  • 一、原理
  • 二、例题
    • 1.二分查找
    • 2.使用二分查找确定target左右边界
    • 3.x的平方根


一、原理

条件:数组为有序数组,数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的;

  • 第一种写法:
    在这里插入图片描述
    在这里插入图片描述
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
        while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间,所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间,所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};
  • 第二种写法:
    在这里插入图片描述
    在这里插入图片描述
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
        while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间,在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间,在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

二、例题

1.二分查找

https://leetcode.cn/problems/binary-search/description/

2.使用二分查找确定target左右边界

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

  • 该题目的要点在于非递减数组(升序,但是有可能有重复数字)中寻找target的左右边界,target可能有多个重复值的情况;
  • 时间复杂度需要是O(log N),表明需要使用二分查找确定左右边界,不能采用遍历方法确定边界;
  • 先确定情况:
    • target不再nums区间内;
    • target在nums区间内,但是nums中没有target;
    • nums中有target;

使用二分查找确定边界的原理:
二分查找在没有查找到target的时候,target是在最终的(left, right)这个区间之内的,可以使用这个原理来分别找出左右边界;

  • 确定右边界
    在这里插入图片描述
    当nums[mid]的值小于等于target的时候,选择更新right_border,right_border需要跟着left更新,因为无论是否找到target,最终left一定会指向nums中大于target的数中最小的那个数,就是target的有边界(开区间);
  • 左边界同理;

特殊情况:

  • nums为{2, 2},target为3,最终左右边界输出值为(-2, 2),之间的差值大于1,应该输出左右边界,但是target却不在nums中;
    解决方案:直接在最外面加一个判断target是否属于nums区间的条件;
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        
        int tar_l = leftBorder(nums, target);
        int tar_r = rightBorder(nums, target);
        cout << tar_l << "   " << tar_r << endl;

        if(nums.empty() || (target < nums[0] || target > nums[nums.size() - 1]))
        {
            //target不在nums范围
            res.push_back(-1);
            res.push_back(-1);
        }
        else if(tar_r - tar_l > 1)
        {
            //target存在于nums中
            res.push_back(tar_l + 1);
            res.push_back(tar_r - 1);
        }
        else
        {
            //target不存在于nums中
            res.push_back(-1);
            res.push_back(-1);
        }

        return res;
    }

    //寻找右边界 -- target右边的一个位置
    int rightBorder(vector<int>& nums, int target)
    {
        int right_border = -2;
        int left = 0, right = nums.size() - 1;
        //进行二分查找
        while(left <= right)
        {
            int mid = left + ((right - left) / 2);
            if(nums[mid] > target)//不断缩小右边界
            {
                right = mid - 1;
            }
            else
            {
                //缩小左边界
                //且当找到target时,left继续向右,目的是找到最右边target的位置
                left = mid + 1;
                right_border = left;
                //left最终指向的会是nums中大于target的最小数
            }
        } 
        return right_border;
    }
    
    //寻找左边界
    int leftBorder(vector<int>& nums, int target)
    {
        int left_border = -2;
        int left = 0, right = nums.size() - 1;
        //进行二分查找
        while(left <= right)
        {
            int mid = left + ((right - left) / 2);
            if(nums[mid] < target)//不断缩小左边界
            {
                left = mid + 1;
            }
            else
            {
                //缩小右边界
                //且当找到target时,right继续向右,目的是找到最左边target的位置
                right = mid - 1;
                left_border = right;
                //right最终指向的会是nums中小于target的最大数
            }
        } 
        return left_border;
    }

};

3.x的平方根

https://leetcode.cn/problems/sqrtx/submissions/483798269/

从题目的要求和示例我们可以看出,这其实是一个查找整数的问题,并且这个整数是有范围的。

  • 如果这个整数的平方 恰好等于 输入整数,那么我们就找到了这个整数;
  • 如果这个整数的平方 严格大于 输入整数,那么这个整数肯定不是我们要找的那个数;
  • 如果这个整数的平方 严格小于 输入整数,那么这个整数 可能 是我们要找的那个数(重点理解这句话)。

因此我们可以使用「二分查找」来查找这个整数,不断缩小范围去猜。
方法一:

  • 猜的数平方以后大了就往小了猜;
  • 猜的数平方以后恰恰好等于输入的数就找到了;
  • 猜的数平方以后小了,可能猜的数就是,也可能不是。
class Solution {
public:
    int mySqrt(int x) {
        int min = 0, max = x;
        int res = 0;
        
        while(min <= max)
        {
            int mid = min + (max - min) / 2;
            if((long long)mid * mid <= x)  // 防止乘法溢出
            {
            	// 目标结果的平方小于等于x,寻找出的就是范围内最大的满足平方<=x的数
                min = mid + 1;
                res = mid;
            }
            else
            {
                max = mid - 1;
            }
        }
        return res;
    }
};

方法二:

  • 使用二分查找寻找边界,目标数其实就是左边界
class Solution {
public:
    int mySqrt(int x) {
        int min = 0, max = x;
        int res = 0;
        //寻找左边界
        while(min <= max)
        {
            int mid = min + ((max - min) / 2);
            if((long long)mid * mid < x)
            {
                min = mid + 1;
            }
            else if((long long)mid * mid > x)
            {
                max = mid - 1;
                res = max;
            }
            else
            {
                return mid;
            }
        }
        return res;
    }
};

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

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

相关文章

Hibernate 一级缓存,二级缓存,查询缓存

概念&#xff1a; 1.什么是缓存呢&#xff1f; 缓存&#xff1a;是计算机领域的概念&#xff0c;它介于应用程序和永久性数据存储源之间。 缓存&#xff1a;一般人的理解是在内存中的一块空间&#xff0c;可以将二级缓存配置到硬盘。用白话来说&#xff0c;就是一个存储数据的…

问题 R: 胜利大逃亡(HUST)

#include <deque> #define inf 200000 #include<iostream> #include<queue> using namespace std;// 迷宫坐标 int map[59][59][59] { 0 };// 可访问标记 int visit[51][51][51] { 0 }; // 移动方式 int next1[7][4] { {1,0,0},{-1,0,0}, {0,1,0},{0,-1,…

gitlab安装配置及应用

安装 ##安装依赖 yum install -y curl policycoreutils-python openssh-server perl#上传包 rz gitlab-jh-16.5.2-jh.0.el7.x86_64.rpm 安装 yum install gitlab-jh-16.0.3-jh.0.el7.x86_64.rpm 初始化并启动 # 以下两种方法都可以配置访问地址&#xff0c;第一种需要在yum安…

千字文||无聊又数了一下千字文字数

千字文的字数去除标点符号真的整整一千个不多的不少 该文章无技术含量&#xff0c;仅三字经原文&#xff0c;学技术的同学可以止步了 千字文&#xff08;原文&#xff09; 【作者】周兴嗣 【朝代】南北朝 天地玄黄&#xff0c;宇宙洪荒。 日月盈昃&#xff0c;辰宿列张。 寒来…

【LeetCode】104. 二叉树的最大深度

104. 二叉树的最大深度 难度&#xff1a;简单 题目 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 …

Spring框架学习 -- 创建与使用

目录 (1) 创建spring 项目 ① 创建maven项目 ②添加spring框架支持 ③ 添加启动项 (2) 创建 Bean对象 (3) 将Bean注入到容器 (4) 获取Bean对象 (5) 注意事项 (6) Spring的创建和使用流程图 创作不易多多支持 (1) 创建spring 项目 首先我们使用的开发工具为idea 专业版…

渲染器——双端Diff算法

简单 Diff 算法利用虚拟节点的 key 属性&#xff0c;尽可能地复用 DOM 元素&#xff0c;并通过移动 DOM 的方式来完成更新&#xff0c;从而减少不断地创建和销毁DOM 元素带来的性能开销。但是&#xff0c;简单 Diff 算法仍然存在很多缺陷&#xff0c;这些缺陷可以通过双端 Diff…

[userfaultfd] 2019-BalsnCTF_KrazyNote

前言 题目不算难, 但是这代码逆向可逆死个人:) 悲悲悲 程序分析 内核版本: v5.1.9 保护: 开了 kaslr, smep, smap. 现在的题目基本都开了, 都不用看. 其中 note 模块中注册了一个 misc 设备, 其函数表中就只有 note_open 和 note_unlocked_ioctl 两个函数, 其中 note_open…

GAMES101—Lec 05~06:光栅化

目录 概念回顾&#xff08;个人理解&#xff09;光栅化1.采样2.采样出现的问题&#xff1a;走样 反走样 概念回顾&#xff08;个人理解&#xff09; 屏幕&#xff1a;在图形学中&#xff0c;我们认为屏幕是一个二维数组&#xff0c;数组里的每一个元素为一个二维像素。 光栅化…

1.8w 字详解 SQL 优化

来源&#xff1a;捡田螺的小男孩 1、MySQL的基本架构 2、SQL优化 3、explain执行计划常用关键字详解 很多朋友在做数据分析时&#xff0c;分析两分钟&#xff0c;跑数两小时&#xff1f; 在使用SQL过程中不仅要关注数据结果&#xff0c;同样要注意SQL语句的执行效率。 本文…

【阿里云】图像识别 摄像模块 语音模块

USB 摄像头模块测试及配置 一、首先将 USB 摄像头插入到 Orange Pi 开发板的 USB 接口中二、然后通过 lsmod 命令可以看到内核自动加载了下面的模块三、通过 v4l2-ctl 命令可以看到 USB 摄像头的设备节点信息为 /dev/video0四、使用 fswebcam 测试 USB 摄像头五、使用 motion …

C#期末速成推荐看的知识和免费视频

【拯救者】C#期末速成 (基础讲解整套题讲解文档下载) 4K ​ 这里讲的是【 &#x1f337;速成&#x1f337; 速成&#x1f337; 速成】版本&#xff0c;按课本章节来&#xff0c; 抽取重点&#xff0c;翻译为人话&#xff01;&#xff01;&#xff01;&#x1f49d; 文末附上 免…

Python+Selenium定位不到元素常见原因及解决办法(报:NoSuchElementException)

这篇文章主要介绍了PythonSelenium定位不到元素常见原因及解决办法(报&#xff1a;NoSuchElementException),文中通过示例代码介绍的非常详细&#xff0c;对大家的学习或者工作具有一定的参考学习价值&#xff0c;需要的朋友们下面随着小编来一起学习学习吧 在做web应用的自动…

两种Deformable Attention的区别

先分别写一下流程 Deformable DETR(2020)的Deformable Attention 解释&#xff1a; Deformable Attention如下图所示K3, M3K是指每个zq会和K个offset算attention&#xff0c;M是指M个head&#xff0c; z q z_q zq​有NHW个&#xff1a; 参考点&#xff1a;reference points&am…

基于Apache部署虚拟主机网站

文章目录 Apache释义Apache配置关闭防火墙和selinux 更改默认页内容更改默认页存放位置个人用户主页功能基于口令登录网站虚拟主机功能基于ip地址相同ip不同域名相同ip不同端口 学习本章完成目标 1.httpd服务程序的基本部署。 2.个人用户主页功能和口令加密认证方式的实现。 3.…

gitlab安装以及创建用户创建组,修改密码 邮箱配置 数据备份与恢复--保姆级教学!

GitLab是一种基于Web的Git仓库管理工具&#xff0c;它允许您在组织或个人级别上创建和管理Git仓库&#xff0c;以便在一个中心位置上执行代码管理和协作工作。GitLab提供了强大的功能&#xff0c;如代码审查、问题跟踪、CI/CD、容器注册表、Wiki和持续集成等。 以下是GitLab的…

【高级网络程序设计】Week2-3 HTML

一、The Basics 1. HTML&HTML file HTMLMarkup languageHyper Text Markup LanguageHTML fileText file with markup tags.htm/.html extension Create an html file Open an editor Type: <html><head><titile><body> Save it as .html Open i…

了解:iperf网络性能测试工具

当进行网络性能测试时&#xff0c;可以使用iperf这个开源工具。iperf是一款网络测试工具&#xff0c;它能够测试TCP或UDP带宽质量&#xff0c;以及单向和双向吞吐量。使用iperf进行网络性能测试首先需要在被测试的两台计算机上安装iperf。 如何安装iperf&#xff1f; 在Debia…

日志技术logback

一&#xff0c;日志概括 二&#xff0c;日志技术的特点 三&#xff0c;日志技术的体系 三&#xff0c;入门 四&#xff0c;案例 package XinZheng;import org.slf4j.Logger; import org.slf4j.LoggerFactory;public class Main58 {//1,创建一个Logger日志对象public static fi…