【基础算法】二分查找

1.二分查找

二分查找

思路:

朴素二分模版

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if(nums[mid] < target) l = mid + 1;
            else if(nums[mid] > target) r = mid - 1;
            else return mid;
        }
        return -1;
    }
};

2.在排序数组中查找元素的第一个和最后一个位置

在排序数组中查找元素的第一个和最后一个位置

思路:

二分左端点和二分右端点模版题

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 处理边界情况
        if(nums.size() == 0) return {-1,  -1};

        // 记录开始位置
        int begin = 0;

        // 二分左端点
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        // 判断结果是否成立
        if(nums[left] != target)
            return {-1, -1};
        else 
            begin = left;
        // 更新right位置
        right = nums.size() - 1;
        // 二分右端点
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {begin, left};
    }
};

3.搜索插入位置

搜索插入位置

思路:

 根据插入位置来分析出一个二分性

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        // 记得处理边界情况
        if(nums[left] < target) return left + 1;
        else return left; 
    }
};

 4.x的平方根

x的平方根

 

 思路:

记得处理边界情况

class Solution {
public:
    int mySqrt(int x) {
        //处理边界情况
        if(x < 1) return 0;
        int left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

 5.山顶数组的封顶索引

山顶数组的封顶索引

思路:

切记首位置和最后一个位置无需二分

二分查找并不需要完全按照有序的性质来确定是否使用,

我们只需要找出一个二分性就可使用二分查找算法。 

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

6.寻找峰值

寻找峰值

 思路:

二分右端点

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left= 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

7.寻找旋转数组中的最小值 

寻找旋转数组中的最小值

 思路:

旋转数组,可以画个图

 以一个参照点来找出二分性

以最右边端点为参照最合适,无需考虑边界问题

当选择左边端点时需要考虑当一个旋转 数组刚好就是原数组时,需要特别处理!

class Solution {
public:
    int findMin(vector<int>& nums) {
        int x = nums[nums.size() - 1];
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] > x) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};

8.点名

点名

思路:

这个题解法有很多种!

1.暴力查找

2. 哈希表

3.位运算

4.二分查找

class Solution {
public:
    int takeAttendance(vector<int>& r) {
        int left = 0, right = r.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(r[mid] == mid) left = mid + 1;
            else right = mid;
        }
        //处理细节问题
        if(r[left] == left) return left + 1;
        else return left;
    }
};

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

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

相关文章

综合性练习(后端代码练习1)——加法计算器

目录 一、准备工作 二、约定前后端交互接口 1、概念介绍 2、需求分析 3、接口定义 请求参数 响应数据 三、服务器代码 四、前端页面代码 五、运行测试 遇到问题如何解决&#xff1f; 需求&#xff1a;输入两个整数&#xff0c;点击 “点击相加” 按钮&#xff0c;显…

JAVA顺序表相关习题1

1.笔试题:cvte str1 :welcome to cvte str2:come 描述:删除第一个字符串当中出现的所有的第二个字符串的字符!结果:wlt vt 要求 用ArrayList完成! public class Test {public static List<Character> findSameWords(String u1, String u2){List<Character> listn…

前端请求没问题,后端正常运行,但查不出数据

写代码时写得快了些&#xff0c;Orders.的订单状态写错了CONFIRMED 改成COMPLETED

二、再识VUE-MVVM

一、初识VUE 二、再识VUE-MVVM 三、VUE数据代理 MVVM Vue.js 专注于 MVVM 模型的 ViewModel 层。它通过双向数据绑定把 View 层和 Model 层连接了起来。实际的 DOM 封装和输出格式都被抽象为了 Directives 和 Filters。 ViewModel 一个同步 Model 和 View 的对象。在 Vue.js…

汇川AM400PLC编码器转速测量功能块(M法测速)

M法测速的原理和相关代码,大家可以参考相关专栏文章,常用链接如下: 1、编码器M法测速仿真 编码器M法测速仿真(Simulink)_mt法测速 simulink-CSDN博客文章浏览阅读2k次。编码器M法和T法测速的详细讲解可以参看下面的文章链接,这里不再赘述,这里主要介绍Simulink里建模仿真…

(06)vite与ts的结合

文章目录 系列全集package.json在根目录创建 tsconfig.json 文件在根目录创建 vite.config.ts 文件index.html额外的类型声明 系列全集 &#xff08;01&#xff09;vite 从启动服务器开始 &#xff08;02&#xff09;vite环境变量配置 &#xff08;03&#xff09;vite 处理 c…

详细介绍如何使用YOLOv9 在医疗数据集上进行实例分割-含源码+数据集下载

深度学习彻底改变了医学图像分析。通过识别医学图像中的复杂模式,它可以帮助我们解释有关生物系统的重要见解。因此,如果您希望利用深度学习进行医疗诊断,本文可以成为在医疗数据集上微调YOLOv9 实例分割的良好起点。 实例分割模型不是简单地将区域分类为属于特定细胞类型,…

新质生产力实践,我用chatgpt开发网站

是的&#xff0c;我用chatgpt开发了一个网站&#xff0c;很轻松。 我之前一点不懂前端&#xff0c;也没有网站开发的代码基础&#xff0c;纯正的0基础。 从0开始到最后成品上线&#xff0c;时间总计起来大致一共花了2-3周的时间。 初始想法我是想给我公司开发一个网站&#…

3月8日是星期六

突然有查询特殊条件日期的需求。 <html> <title>3月8日是星期六</title> <center> <h1 id"h1"></h1> <div id"div"></div> </center> <script> var weekday [星期日, 星期一, 星期二, 星期…

Eclipse:-Dmaven.multiModuleProjectDirectory system propery is not set.

eclipse中使用maven插件的时候&#xff0c;运行run as maven build的时候报错 -Dmaven.multiModuleProjectDirectory system propery is not set. Check $M2_HOME environment variable and mvn script match. 可以设一个环境变量M2_HOME指向你的maven安装目录 M2_HOMED:\Apps\…

echarts开发技巧

tooltip 提示框组件相关的行为&#xff0c;必须引入提示框组件后才能使用。 tooltip: {trigger: axis,axisPointer: {type: cross,label: {backgroundColor: #6a7985,},},//为弹出层的value值增加百分号valueFormatter: function (value) {return value %}, }, tooltip.axi…

碳课堂|快速了解标准要点:ISO 14064-1

为了提高企业组织碳排放报告信誉度&#xff0c;国际标准化组织&#xff08;ISO&#xff09;发布了ISO14064 标准&#xff08;全称&#xff1a;《ISO 14064-1组织层次上对温室气体排放和清除的量化和报告的规范及指南》&#xff09;&#xff0c;报告中详细规定了公司温室气体清单…

确定性最大似然(DML)估计测角

1. 最大似然函数 贝叶斯方法是基于统计理论的一种经典方法&#xff0c;适合于有关参数估计问题。最大似然 (Maximum Likelihood&#xff0c;ML) 估计方法就是贝叶斯估计方法的一种特例&#xff0c;是在已知高斯噪声情况下的贝叶斯最优估计。在ML算法中&#xff0c;观测所得信号…

品牌出海新篇章:独立站构建与流量转化策略

在当今数字化时代&#xff0c;品牌出海已成为许多企业拓展国际市场的重要途径之一。在这个过程中&#xff0c;构建一个高效、专业的独立站&#xff0c;成为了品牌出海的重要一环。独立站不仅有助于企业塑造独特的品牌形象&#xff0c;更能通过精准的营销策略提高流量和转化率&a…

乘用车整车太阳光模拟加速老化试验太阳光模拟器

1.阳光模拟试验介绍 太阳辐射会对室外停放的汽车内外饰件产生热效应和光化学效应&#xff0c;影响汽车内外饰件的外观、性能&#xff0c;对汽车质产生不利影响。按照汽车产环境试验标准的要求&#xff0c;汽车在研制定型之前应进行太阳辐射试验&#xff0c;以考虑其对太阳辐射环…

微服务之分布式理论zookeeper概述

一、分布式技术相关的理论 CAP理论 CAP定理(CAP theorem)&#xff0c;⼜被称作布鲁尔定理(Eric Brewer)&#xff0c;1998年第⼀次提出. 最初提出是指分布式数据存储不可能同时提供以下三种保证中的两种以上: (1) ⼀致性(Consistency): 每次读取收到的信息都是最新的; (2) …

探索主播美颜工具与直播美颜SDK的技术奥秘

主播的形象美化是至关重要的一环&#xff0c;而实现这一目标的关键在于美颜工具和直播美颜SDK。接下来&#xff0c;我们将一同深入探索这些技术的奥秘&#xff0c;揭示它们背后的原理和工作方式。 一、美颜工具的背后 美颜工具是一类应用软件&#xff0c;旨在通过图像处理技术…

树莓派点亮LED灯

简介 使用GPIO Zero library 的 Python库实现点亮LED灯。接线 树莓派引脚参考图如下&#xff1a; LED正极 接GPIO17 LED负极 接GND 权限 将你的用户加到gpio组中&#xff0c; 否则无法控制GPIO sudo usermod -a -G gpio 代码 from gpiozero import LED from time impor…

基于H.264的RTP打包中的组合封包以及分片封包结构图简介及抓包分析;FU-A FU-B STAP-A STAP-B简介;

H.264视频流的RTP封装类型分析&#xff1a; 前言&#xff1a; 1.RTP打包原则&#xff1a; RTP的包长度必须要小于MTU(最大传输单元)&#xff0c;IP协议中MTU的最大长度为1500字节。除去IP报头&#xff08;20字节&#xff09;、UDP报头&#xff08;8字节&#xff09;、RTP头&a…

【Axure高保真原型】拖动穿梭选择器

今天和大家分享拖动穿梭选择器的原型模板&#xff0c;我们可以拖动两个选择器里的选项标签&#xff0c;移动到另外一个选择器里。那这个原型模板是用中继器制作的&#xff0c;所以使用也很方便&#xff0c;只需要在中继器表格里填写选项信息&#xff0c;即可自动生成交互效果&a…