【二分查找】

二分查找

  • 704. 二分查找
  • 35. 搜索插入位置
  • 34. 在排序数组中查找元素的第一个和最后一个位置
  • 结语

704. 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

链接: 二分查找

这个题是一个最基础的二分查找题目,需要你写出二分查找最基础的模板出来。
二分查找有许多的边界问题,每一次边界的处理都要坚持根据区间的定义来操作
,这就是循环不变量规则。

由题可知,该数组是一个升序的有序整型数组,
在这里插入图片描述
定义一个l变量,一个r变量,一个mid,分别表示的左值,右值,中值。
然后对每一次的mid中值进行一次check,当循环正常结束就是没有target值,
返回-1.

代码:

int search(int* nums, int numsSize, int target){
    
    int left=0,right=numsSize-1;
    int mid=(left+right)/2;
    while(left<right)
    {
        if(nums[mid]>=target)
        {
            right=mid;
        }
        else left=mid+1;

        mid=(left+right)/2;
    }
    if(nums[left]==target)
    return left;

    return -1;

}

35. 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

输入: nums = [1,3,5,6], target = 5
输出: 2

输入: nums = [1,3,5,6], target = 2
输出: 1

输入: nums = [1,3,5,6], target = 7
输出: 4

链接: 搜索插入位置

这道题是二分查找的稍微进阶,相较于上一题需要考虑边界情况,
以及最后的返回值。

将上一题的代码拷贝下来


while(left<=right)
{
    if(nums[mid]==target)
    {
           return mid;
    }
    if(nums[mid]>target)
    {
        right=mid-1;
    }
    if(nums[mid]<target)
    {
        left=mid+1;
    }
    mid=(left+right)/2;

这是部分代码,从题中可知,
如果在遍历的时候找到与target对应的值,那么可以直接返回此时的下标mid
如果没有找到的话,循环结束后l,r,mid,这三个下标哪个是正确的返回值呢。

由题意得,返回的是按照值大小顺序插入的位置,所以返回了l的下标。

代码:

int searchInsert(int* nums, int numsSize, int target){
    
    int right =numsSize-1;
    int left=0;
    int mid=(right+left)/2;
   
    while(left<=right)
    {
        if(nums[mid]==target)
        {
               return mid;
        }
        if(nums[mid]>target)
        {
            right=mid-1;
        }
        if(nums[mid]<target)
        {
            left=mid+1;
        }
        mid=(left+right)/2;
    }
    return left;


}

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

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

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

解题思路:
1.题目要求找出等于target大小的数组元素下标的开始位置和结束位置。
2.也就说需要进行两次二分查找,一次找出开始位置,一次找出结束位置
3.找出开始位置:

  1. 当数组中有target元素的时候,我们可以将其分为两个部分
  2. 第一个部分范围为所有 小于target的值
  3. 第二部分则为所有 大于等于target的值
  4. 由此可知,第二部分的开头位置的下标即为所求

代码:

        int l = 0;
        int r = nums.size() - 1;
        int mid = (l + r) / 2;
        while (l < r)
        {
            if (nums[mid] >= target)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
            mid = (l + r) / 2;
        }

4.找出结束位置下标:(同上)

  1. 当数组中有target元素的时候,我们可以将其分为两个部分
  2. 第一个部分范围为所有 小于等于target的值
  3. 第二部分则为所有 大于target的值
  4. 由此可知,第一部分的结束位置的下标即为所求

注意: 此时随着循环更新的是l的值,所以更新方式应改变。mid=(l+r+1)/2
代码:

l = 0;
r = nums.size() - 1;
mid = (l + r+ 1) / 2;
while (l < r)
{
    if (nums[mid] <= target)
    {
        l = mid;
    }
    else
    {
        r = mid - 1;
    }
    mid = (r + l+ 1) / 2;
}

每次求出也要检查所求下标对应的值是否为target。

代码:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        //特殊情况处理
        if(nums.size()==0)
        {
        ans.push_back(-1);
        ans.push_back(-1);
        return ans;
        }
        //初始位置
        int l = 0;
        int r = nums.size() - 1;
        int mid = (l + r) / 2;
        while (l < r)
        {
            if (nums[mid] >= target)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
            mid = (l + r) / 2;
        }
        if (nums[l] == target) ans.push_back(l);
        else ans.push_back(-1);
        
        //结束位置
        l = 0;
        r = nums.size() - 1;
        mid = (l + r+ 1) / 2;
        while (l < r)
        {
            if (nums[mid] <= target)
            {
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
            mid = (r + l+ 1) / 2;
        }
        if (nums[r] == target) ans.push_back(r);
        else ans.push_back(-1);

        return ans;
    }
};

结语

本期的二分查找到此结束,希望对各位有所帮助

我是Tom-猫
如果觉得有帮助的话,记得
一键三连哦ヾ(≧▽≦*)o。
在这里插入图片描述

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

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

相关文章

mybatis中获取参数的两种方式:${}和#{}

目录 1.#{} 2.${} 3.总结 1.#{} 本质是占位符赋值 示例及执行结果&#xff1a; 结论&#xff1a;通过执行结果可以看到&#xff0c;首先对sql进行了预编译处理&#xff0c;然后再传入参数&#xff0c;有效的避免了sql注入的问题&#xff0c;并且传参方式也比较简单&#xf…

Python制作9行最简单音乐播放器?不,我不满足

人生苦短 我用python 好久不见啦~这次就来给大家整个大福利 ~ 源码资料电子书:点击此处跳转文末名片获取 最简单的9行代码音乐播放器如下&#xff1a; import time import pygamefile r歌曲路径 pygame.mixer.init() print(正在播放,file) track pygame.mixer.music.load(f…

计算机面试常见问答题目

英语口语 自我介绍 Hello, teachers. My name is Wang Xu. I come from Ningxia. I graduated from the School of Computer Science, Xi an Jiaotong University, majoring in Internet of Things. Next, I will introduce myself from four aspects. First of all, I studi…

Java开发 - ELK初体验

前言 前面我们讲过消息队列&#xff0c;曾提到消息队列也具有保存消息日志的能力&#xff0c;今天要说的EL看也具备这个能力&#xff0c;不过还是要区分一下功能的。消息队列的日志主要指的是Redis的AOF&#xff0c;实际上只是可以利用了消息队列来保存&#xff0c;却并不是消…

网络编程1(网络背景知识)

A给B发送消息如何保证数据一定能够发送到B的主机上&#xff0c;而不是其他地方 通过IP地址可以实现网络中制定的两个主机之间的通信&#xff0c;除此之外还要确定是哪个进程来处理&#xff0c;这里就用到端口&#xff08;port&#xff09; 端口—在一台主机上用于唯一标识一个…

MySQL索引特性

文章目录为什么要有索引&#xff1f;认识磁盘磁盘的结构磁盘的盘片结构定位扇区磁盘随机访问 (Random Access)与连续访问 (Sequential Access)MySQL与磁盘交互索引的理解测试主键索引索引的原理索引结构是否可以使用其他数据结构B树 vs B树聚簇索引 vs 非聚簇索引为什么要有索引…

基于深度学习的犬种识别软件(YOLOv5清新界面版,Python代码)

摘要&#xff1a;基于深度学习的犬种识别软件用于识别常见多个犬品种&#xff0c;基于YOLOv5算法检测犬种&#xff0c;并通过界面显示记录和管理&#xff0c;智能辅助人们辨别犬种。本文详细介绍博主自主开发的犬种检测系统&#xff0c;在介绍算法原理的同时&#xff0c;给出Py…

分布式微服务架构下网络通信的底层实现原理

在分布式架构中&#xff0c;网络通信是底层基础&#xff0c;没有网络&#xff0c;也就没有所谓的分布式架构。只有通过网络才能使得一大片机器互相协作&#xff0c;共同完成一件事情。 同样&#xff0c;在大规模的系统架构中&#xff0c;应用吞吐量上不去、网络存在通信延迟、我…

Qt音视频开发26-监控画面各种图形绘制设计

一、前言 视频监控系统做到后面&#xff0c;逐渐需要搭配人工智能算法&#xff0c;将算法计算后的信息以OSD标签以及方框各种图形的信息显示到视频中&#xff0c;这种当然和OSD一样也是有两种方式&#xff0c;一种是源头就贴好了&#xff0c;一种是将结果发给软件这边解析绘制…

专项攻克——死锁

文章目录O、死锁定义一、 常见的java死锁代码1. synchronized等待对象释放&#xff0c;导致死锁2. CountDownLatch计数等待&#xff0c;导致死锁二、怎么避免死锁2.1 死锁的四个必要条件2.2 避免死锁2.3 常见的避免死锁技术三、java程序出现死锁&#xff0c;怎么解除&#xff1…

Vue使用的编辑器

作者简介&#xff1a;一名计算机萌新、前来进行学习VUE,让我们一起进步吧。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;我叫于豆豆吖的主页 目录 前言 一.vue常用的IDE工具Visual Studio Code 3. 汉化教程 4.常用快捷键 5. Visual Studio C…

瑞萨Renesas RA2L1 开发板测评(1)--keil环境配置

前言&#xff08;1&#xff09;首先感谢李肯前辈的活动&#xff0c;从而申请到了RA2L1开发板的测评。&#xff08;2&#xff09;本文将会简单介绍此开发的Renesas RA2L1 开发板的前期配置。需要注意的是&#xff0c;MDK版本要5.30 以上。MDK下载链接&#xff1b;&#xff08;3&…

计算机中的浮点数运算

计算机中的浮点数 计算机中以固定长度存储浮点数的方式&#xff0c;造成了浮点数运算过程容易产生上溢和下溢。以float32为例, 其标记位占1bit,指数位占8bit,小数部分占23bit 经典下溢场景 不满足精度导致截断误差 #include <iostream> #include <iomanip> usin…

一行代码“黑”掉任意网站

文章目录只需一行代码&#xff0c;轻轻一点就可以把任意网站变成暗黑模式。 首先我们先做一个实验&#xff0c;在任意网站中&#xff0c;打开浏览器开发者工具(F12)&#xff0c;在 C1onsole 控制台输入如下代码并回车&#xff1a; document.documentElement.style.filterinve…

Hive 数据倾斜

数据倾斜&#xff0c;即单个节点任务所处理的数据量远大于同类型任务所处理的数据量&#xff0c;导致该节点成为整个作业的瓶颈&#xff0c;这是分布式系统不可能避免的问题。从本质来说&#xff0c;导致数据倾斜有两种原因&#xff0c;一是任务读取大文件&#xff0c;二是任务…

【MIT 6.S081】Lab2: system calls

本Lab包括两个简单系统调用的实现&#xff0c;进一步熟悉系统调用接口。 笔者用时约1.5h 概述 根据文档说明&#xff0c;当我们添加一个系统调用时&#xff0c;比如第一个任务是添加一个trace&#xff0c;需要进行以下操作&#xff1a; 首先将系统调用的原型添加到user/user…

博客系统实现自动化测试

目录 一、设计博客系统的测试用例 二、利用测试用例进行测试 测试登录页面 界面测试 功能测试 测试博客列表页 界面测试 功能测试 测试博客详情页 界面测试 功能测试 博客编辑页测试 界面测试 功能测试 一、设计博客系统的测试用例 二、利用测试用例进行测…

【Java版oj】day12二进制插入、查找组成一个偶数最接近的两个素数

目录 一、二进制插入 &#xff08;1&#xff09;原题再现 &#xff08;2&#xff09;问题分析 &#xff08;3&#xff09;完整代码 二、查找组成一个偶数最接近的两个素数 &#xff08;1&#xff09;原题再现 &#xff08;2&#xff09;问题分析 &#xff08;3&#xff0…

One-YOLOv5 v1.2.0 Released(支持分类,检测,实例分割)

0x0. 引言0x1. 快速开始0x2. 在COCO上的精度表现 yolov5s-defaultyolov5s-seg 0x3. 在COCO上的单GPU性能表现特性 & bug 修复 特性用户反馈的bug 下个版本的展望附件常用预训练模型下载列表 0x0. 引言 &#x1f31f; v1.2.0同步了ultralytics yolov5的上游分支v7.0 &…

前端入门:HTML5+CSS3+JAAVASCRIPT

1、 初识HTML HTML:Hyper Text Markup Language(超文本标记语言) 。 超文本包括&#xff1a;文字、图片、音频、视频、动画等。 1.1、W3C标准 1.2、HTML基本结构 示例&#xff1a; <!-- DOCTYPE:告诉浏览器&#xff0c;我们要使用什么规划&#xff0c;这里是HTML --> …
最新文章