二分法相关使用

文章目录

  • 1. 在一个有序数组中,找某个数是否存在
  • 2. 在一个有序数组中,找大于等于某个数最左侧的位置
  • 3. 在一个有序数组中, 找小于等于某个数最右侧的位置
  • 4. 局部最大值问题

1. 在一个有序数组中,找某个数是否存在

在线OJ:704. 二分查找

有序数组下的二分思路如下:

  • 由于这里是有序数组, 我们可以可以先得到中点位置, 中点可以把数组分为左右两边;
  • 如果中点位置的值等于目标值, 直接返回中点位置;
  • 如果中点位置的值小于目标值, 则去数组中点左侧按同样的方式查找;
  • 如果中点位置的值大于目标值, 则取数组中点右侧按同样的方式查找;
  • 如果最后没有找到, 则返回 -1.

代码实现如下:

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

2. 在一个有序数组中,找大于等于某个数最左侧的位置

在线OJ: 35. 搜索插入位置

通过题目示例可以知道, 这个题本质上就是在一个有序数组中, 找大于等于某个数最左侧的位置, 如果不存在, 就返回数组长度 (表示插入在最末尾位置).

这个题只需要在 1 代码基础上进行简单改动即可, 在 1 中, 我们找到满足条件的位置就直接返回了; 而在本题中, 因为要找到最左侧的位置, 所以, 在遇到 nums[mid] >= target 的时候, 不用直接返回, 而是先把位置 mid 记录下来, 然后继续去左侧找是否还有满足条件的更左边的位置.

代码实现如下:

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        int ans = nums.length;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

3. 在一个有序数组中, 找小于等于某个数最右侧的位置

和 2 的实现基本是一样的, 就不赘述了, 代码如下:

/**
 * 有序数组中找到 <=num 最右的位置
 */
public static int mostRightIndex(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    int mid = 0;
    int ans = -1;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (arr[mid] <= num) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

4. 局部最大值问题

在线OJ:162. 寻找峰值

思路如下:

题目中已经说明, 对于所有有效的 i 都有nums[i] != nums[i + 1], 所以, 不会出现相邻相等的情况.

假设数组长度为 N, 首先判断 0 号位置的数和 N-1 号位置的数是不是峰值位置; 0 号位置只需要和 1 号位置比较, 如果 0 号位置大; 0 号位置就是峰值位置 (0 号位置位置左边没有元素, 可以认为是无穷小), 可以直接返回.

N-1 号位置只需要和 N-2 号位置比较, 如果 N-1 号位置大, N-1 号位置就是峰值位置 (N-1 号位置右边没有元素, 可以认为是无穷大), 可以直接返回.

如果 0 号位置和 N-1 在上轮比较中均是最小值, 那么数组的样子必然是如下情况:

img

由上图可知, 0 到 1 这段是增长趋势, N-2 到 N-1 这段是下降趋势, 那么峰值位置必在[1…N-2]之间出现;

此时可以通过二分来找峰值位置, 先来到中点位置, 假设中点为 mid, 如果中点位置的值比左右两边的值都大, 即:

arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]

则 mid 位置就是峰值位置, 直接返回即可.

否则, 有如下两种情况:

  • 情况一, mid 位置的值比 mid - 1 位置的值小, 趋势如下图, 此时可以在[1...(mid-1)]区间内继续二分;

img

  • 情况二, mid 位置的值比 mid + 1 位置的值小, 趋势如下图, 此时可以在[(mid+1)...(N-2)]区间内继续二分;

img

如果最后都没找到, 返回 -1 即可.

代码实现如下:

class Solution {
    public int findPeakElement(int[] arr) {
        int len = arr.length;
        if (arr == null || len == 0) {
            return -1;
        }
        if (len == 1) {
            return 0;
        }
        if (arr[0] > arr[1]) {
            return 0;
        }
        if (arr[len - 1] > arr[len - 2]) {
            return len - 1;
        }

        int left = 1;
        int right = len - 2;
        int mid= 0;
        while (left <= right) {
            mid = left + (right-left) / 2;
            if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            if (arr[mid] < arr[mid - 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

补充一下如果想要实现找局部最小值的话, 思路是一样的, 把代码符号改改就行了, 代码如下:

/**
 * 局部最小值问题
 * arr数组中的元素直接一定是相邻不相等的元素
 * 可以是无序的
 */
// 返回任意一个局部最小值即可
public static int oneMinIndex(int[] arr) {
    int len = arr.length;
    if (arr == null || len == 0) {
        return -1;
    }
    if (len == 1) {
        return 0;
    }
    if (arr[0] < arr[1]) {
        return 0;
    }
    if (arr[len - 1] < arr[len - 2]) {
        return len - 1;
    }

    int left = 1;
    int right = len - 2;
    int mid= 0;
    while (left <= right) {
        mid = (left + right) / 2;
        if (arr[mid] > arr[mid - 1]) {
            right = mid - 1;
        } else if (arr[mid] > arr[mid + 1]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    
    return -1;
}

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

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

相关文章

几种常见时间复杂度实例分析

多项式量级 常量阶 O(1) 对数阶 O(logn) 线性阶 O(n) 线性对数阶 O(nlogn) 平方阶O(n2 ),立方阶O(n3 )...k次方阶O(nk) 非多项式量级&#xff08;NP&#xff08;Non-Deterministic Polynomial&#xff0c;非确定多项式&#xff09;问题&#xff09; 指数阶O(2n) 阶乘阶…

Android WebRtc+SRS/ZLM视频通话(1):虚拟机安装Ubuntu

Android WebRtcSRS/ZLM视频通话&#xff08;1&#xff09;&#xff1a;虚拟机安装Ubuntu 来自奔三人员的焦虑日志 秉着没事找事的原则&#xff0c;这里直接从服务器安装开始说起&#xff0c;也当记录自己这一路以来的愚昧之举&#xff0c;由于没有物理服务器&#xff0c;这里以…

MySQL 精选 35 道面试题大厂稳了(含答案)

MySQL 精选 35 道面试题 1.说一下 MySQL 执行一条查询语句的内部执行过程&#xff1f;2.MySQL 查询缓存有什么优缺点&#xff1f;3.MySQL 的常用引擎都有哪些&#xff1f;4.常用的存储引擎 InnoDB 和 MyISAM 有什么区别&#xff1f;5.什么叫回表查询&#xff1f;6.如果把一个 I…

95后阿里P7晒出工资单:狠补了这个,真香···

最近一哥们跟我聊天装逼&#xff0c;说他最近从阿里跳槽了&#xff0c;我问他跳出来拿了多少&#xff1f;哥们表示很得意&#xff0c;说跳槽到新公司一个月后发了工资&#xff0c;月入5万多&#xff0c;表示很满足&#xff01;这样的高薪资着实让人羡慕&#xff0c;我猜这是税后…

TCP的粘包和拆包

UDP有数据边界&#xff0c;TCP是没有数据边界&#xff0c;是流协议。如何拆包&#xff0c;就要靠应用层来处理。 四层网络模型&#xff0c;消息在进入每一层时都会多加一个报头。mac头部记录的是硬件的唯一地址&#xff0c;IP头记录的是从哪来和到哪去&#xff0c;传输层头记录…

优化问题的拉格朗日Lagrange对偶法原理

首先我们定义一般形式的求解x的优化问题&#xff1a; 表示优化的目标函数&#xff0c;上述为最小优化&#xff0c;实际上最大优化可以改写为的形式表示第i个不等式约束表示等式约束 1. Lagrange对偶问题 上述优化问题的拉格朗日Lagrange对偶法求解&#xff0c;是将上述带约束…

【Vue学习笔记6】好用的 Vueuse 工具包

1. 安装Vueuse VueUse 的官方&#xff08;https://vueuse.org/&#xff09;的介绍说这是一个 Composition API 的工具集合&#xff0c;适用于 Vue 2.x 或者 Vue 3.x&#xff0c;用起来和 React Hooks 还挺像的。 VueUse 插件的安装 npm install vueuse/core2. 实现全屏功能 …

【网络安全】记一次杀猪盘渗透实战

看起来非常假的网站&#xff0c;这个网站是没有 cdn 的用的是 thinkphpk 框架搭建的。 先打一波 poc 没有效果 访问一下后台直接在 url 后面加/admin。 一个开源的 cms 还没有验证码尝试用 burp 进行爆破&#xff0c;首先在火狐上设置代理 ip 为 127.0.0.1 代理端口为 8081。 B…

GPT详细安装教程-GPT软件国内也能使用

GPT (Generative Pre-trained Transformer) 是一种基于 Transformer 模型的自然语言处理模型&#xff0c;由 OpenAI 提出&#xff0c;可以应用于各种任务&#xff0c;如对话系统、文本生成、机器翻译等。GPT-3 是目前最大的语言模型之一&#xff0c;其预训练参数超过了 13 亿个…

ChatGPT终于被我问到胡说八道的程度了!

问&#xff1a;Python是强类型语言&#xff0c;还是弱类型语言 chatgpt&#xff1a;Python是强类型语言。Python很少会隐式地转换变量的类型&#xff0c;所以Python是强类型的语言 问&#xff1a;什么是强类型语言 chatgpt&#xff1a;强类型语言是指在编程语言中&#xff0…

Packet Tracer - 配置交换机端口安全

Packet Tracer - 配置交换机端口安全 地址分配表 设备 接口 IP 地址 子网掩码 S1 VLAN 1 10.10.10.2 255.255.255.0 PC1 NIC 10.10.10.10 255.255.255.0 PC2 NIC 10.10.10.11 255.255.255.0 非法笔记本电脑 NIC 10.10.10.12 255.255.255.0 目标 第 1 部…

MTK6765安卓智能模组5G核心板联发科MTK方案主板开发板

联发科MTK6765这是一款12纳米八核A53处理器&#xff0c;最高运行速度可达2.3GHz。它使用Android 9.0操作系统&#xff0c;配备2G16G内存&#xff0c;也支持其他选项1G/3G/4G8G/32G/64G。 此外&#xff0c;它支持全球主流频段&#xff0c;包括默认的国内频段以及2G GSM、2G/3G E…

学生台灯什么牌子好对眼睛好?专业护眼灯的学生台灯分享

据报告统计&#xff0c;2022年我国儿童青少年总体近视率为52.7%&#xff0c;其中6岁儿童为14.3%&#xff0c;小学生为35.6%&#xff0c;初中生为71.1%&#xff0c;高中生为80.5%&#xff0c;这些数据让人不寒而栗&#xff01; 专家表示&#xff0c;导致儿童青少年近视的因素&am…

离散数学下--- 代数系统

代数系统 定义&#xff1a; 代数系统是用代数运算构造数学模型的方法。 • 通过构造手段生成&#xff0c;所以也称代数结构 • 代数运算&#xff1a;在集合上建立满足一定规则的运算系统 &#xff08;一&#xff09;二元运算 二元运算的定义 二元运算需要满足的两个条件&a…

在Ubuntu18.04中安装uWebSockets库

目录 1.下载uWebSockets库2.下载uSockets3.安装openssl开发包4.编译首先说明这里使用的Ubuntu版本为18.04。 1.下载uWebSockets库 下载uWebSockets库有两种方式,一是终端,从Github中克隆uWebSockets库到Ubuntu本地文件夹,二是打开uWebSockets库下载链接自己下载到Windows,然…

Qt音视频开发38-ffmpeg视频暂停录制的设计

一、前言 基本上各种播放器提供的录制视频接口,都是只有开始录制和结束录制两个,当然一般用的最多的也是这两个接口,但是实际使用过程中,还有一种可能需要中途暂停录制,暂停以后再次继续录制,将中间部分视频不需要录制,跳过这部分不需要的视频,而且录制的视频文件必须…

BoldReports Embedded Reporting 5.1 Crack

Embed Paginated Reports 嵌入式报告平台&#xff0c;商业智能报告解决方案&#xff0c;探索满足各种业务需求的报告功能&#xff0c;所有功能View Features&#xff0c;像素完美报告&#xff0c;创建像素完美的分页业务报表&#xff0c;随处部署&#xff0c;选择适合您的部署环…

一文了解获得 Zebec Labs 投资的 Coral Finance,空投计划或在不久推出

在前不久&#xff0c;Zebec Labs宣布对链上衍生品协议Coral Finance进行150万美元的投资&#xff0c;以帮助该协议完成早期启动并&#xff0c;并在后续持续的为其提供孵化支持。Coral Finance将在不久部署在Nautilus Chain主网上。据了解&#xff0c;Coral Finance是Nautilus C…

RabbitMQ入门Demo 简单模式

出现的问题,原本4个操作,要么全部执行,要么全部不执行------->强一致性 但是现在分开了-----------最终一致性 强一致性&#xff1a;指在消息传递的过程中&#xff0c;系统会确保每个消息被精确地按照发送的顺序被传递&#xff0c;并且每个消息都会被正确地处理。强一致性…

GaussDB数据库基础函数介绍-下

接上一篇&#xff0c;本节继续介绍GaussDB数据库常用基础函数 目录 5、范围函数 6、窗口函数 7、聚集函数 8、安全函数 9、系统信息函数 10、动态脱敏函数 GaussDB常用基础函数介绍与示例 5、范围函数 在GaussDB数据库中&#xff0c;范围函数是指用于处理数据库范围的函…
最新文章