详解二分法查找目标值/二分法查找上下界的两种写法

2024-04-02 14:20

本文主要是介绍详解二分法查找目标值/二分法查找上下界的两种写法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文中默认数组呈升序。

💡 绝对不能使用left = cur这种更新,由于整数除法取下界,left不更新会导致循环无法结束

寻找与target相等

  1. 可以用(l < r)写法,末尾r==l需要检查是否满足条件,满足则输出,不满足则输出-1
  2. 可以用(l<=r) 写法,末尾输出r 不需要检查是否满足条件,不满足的情况下r为-1,因此结果r可能会超出数组索引,注意不要对此进行nums[r]的检查
// ==
// Method1 : left=mid+1, right=mid, 此时最优解为最后的重合解(若可行)
// 遍历直至left = right,左右重合时退出循环,此时重合解若可行,即为答案
int BinSearch1(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l < r) {mid = (l+r)/2;if (nums[mid] == target)return mid;else if (nums[mid] < target) {l = mid + 1;}elser = mid;}if (nums[r] == target)return r;return -1;
}// ==
// Method2 : left=mid+1, right=mid-1, 此时最优解需要另外记录
// 遍历直至left > right,左右重合时仍然进入循环并进行结果记录
int BinSearch2(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l <= r) {mid = (l+r)/2;if (nums[mid] == target)return mid;else if (nums[mid] < target) {l = mid + 1;}elser = mid - 1;}return r;
}

寻找第一个小于(等于)target

💡 需要使用(l<=r) 的写法

因为查找≤时不满足条件更新的是右界,满足条件下更新左界;

如果采用(l<r)写法:

  • 更新左界如果使用l = mid+1 ,由于mid此时满足条件,会导致新区间错失满足条件的点,答案错误
  • 如果使用l=mid,由于mid=(l+r)/2整数除法取下界,某些情况下左界会不更新,从而引起循环无法结束,程序错误

综上,在升序区间查找≤时只能采用(l≤r) 的写法,并通过r输出最终结果:若无满足条件的元素,将会使得r==-1

// <
int BinLBound(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l <= r) {mid = (l+r)/2;// 先更新不满足条件if (nums[mid] >= target) {r = mid - 1;}elsel = mid + 1;}return r;
}// <=
int BinLEBound(vector<int> nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l <= r) {mid = (l+r)/2;if (nums[mid] > target)r = mid - 1;elsel = mid + 1;}return r;
}

寻找第一个大于(等于)target

  1. 可以用(l<r)
  2. 可以用(l<=r)
// >
int BinHBound(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l < r) {mid = (l+r)/2;if (nums[mid] <= target)l = mid + 1;elser = mid;}if (nums[r] > target)return r;return -1;
}
// >=
int BinHEBound(vector<int> &nums, int target) {int l = 0;int r = nums.size()-1;int mid;while (l < r) {mid = (l+r)/2;if (nums[mid] < target)l = mid + 1;elser = mid;}if (nums[r] >= target)return r;return -1;
}

整体测试代码

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> nums{-5, 0, 1, 2, 5, 10, 30, 90};int target = 90;cout << BinSearch1(nums, target) << " " << BinSearch2(nums, target) << endl;cout << BinLBound(nums, target)  << " " << BinLEBound(nums, target) << endl;cout << BinHBound(nums, target)  << " " << BinHEBound(nums, target);return 0;
}

这篇关于详解二分法查找目标值/二分法查找上下界的两种写法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/870213

相关文章

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》:本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客

Python函数作用域示例详解

《Python函数作用域示例详解》本文介绍了Python中的LEGB作用域规则,详细解析了变量查找的四个层级,通过具体代码示例,展示了各层级的变量访问规则和特性,对python函数作用域相关知识感兴趣... 目录一、LEGB 规则二、作用域实例2.1 局部作用域(Local)2.2 闭包作用域(Enclos

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

Java内存分配与JVM参数详解(推荐)

《Java内存分配与JVM参数详解(推荐)》本文详解JVM内存结构与参数调整,涵盖堆分代、元空间、GC选择及优化策略,帮助开发者提升性能、避免内存泄漏,本文给大家介绍Java内存分配与JVM参数详解,... 目录引言JVM内存结构JVM参数概述堆内存分配年轻代与老年代调整堆内存大小调整年轻代与老年代比例元空

Python中注释使用方法举例详解

《Python中注释使用方法举例详解》在Python编程语言中注释是必不可少的一部分,它有助于提高代码的可读性和维护性,:本文主要介绍Python中注释使用方法的相关资料,需要的朋友可以参考下... 目录一、前言二、什么是注释?示例:三、单行注释语法:以 China编程# 开头,后面的内容为注释内容示例:示例:四

mysql表操作与查询功能详解

《mysql表操作与查询功能详解》本文系统讲解MySQL表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE

MySQL中的锁机制详解之全局锁,表级锁,行级锁

《MySQL中的锁机制详解之全局锁,表级锁,行级锁》MySQL锁机制通过全局、表级、行级锁控制并发,保障数据一致性与隔离性,全局锁适用于全库备份,表级锁适合读多写少场景,行级锁(InnoDB)实现高并... 目录一、锁机制基础:从并发问题到锁分类1.1 并发访问的三大问题1.2 锁的核心作用1.3 锁粒度分