lower_bound详解

2024-02-25 01:36
文章标签 详解 bound lower

本文主要是介绍lower_bound详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

lower_bound是C++标准模板库(STL)中的一个算法,用于在有序区间中查找第一个大于或等于给定值的元素的位置。这个函数非常有用,特别是当我们需要在有序数据集中进行二分查找时。下面是对lower_bound函数的详细讲解,包括其用法、原理、实现细节以及示例。

1. 函数原型
lower_bound函数的原型如下:

cpp
template <class ForwardIt, class T>  
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
first和last是迭代器,表示要搜索的范围。
value是要查找的值。
返回值是一个迭代器,指向在有序区间[first, last)中第一个大于或等于value的元素。如果找不到这样的元素,则返回last。
2. 用法示例
下面是一个简单的示例,展示如何使用lower_bound函数:

cpp
#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::vector<int> v = {1, 2, 4, 4, 5, 6};  
    int value = 4;  
      
    auto it = std::lower_bound(v.begin(), v.end(), value);  
      
    if (it != v.end()) {  
        std::cout << "Found at index: " << std::distance(v.begin(), it) << std::endl;  
    } else {  
        std::cout << "Not found" << std::endl;  
    }  
      
    return 0;  
}
输出:

bash
Found at index: 2
在这个示例中,我们在有序向量v中查找值4。lower_bound函数返回一个迭代器,指向第一个大于或等于4的元素。我们使用std::distance函数来计算该元素在向量中的索引。

3. 原理与实现细节
lower_bound函数基于二分查找算法实现。二分查找是一种在有序数据集中查找特定元素的算法,其时间复杂度为O(log n)。lower_bound函数通过不断将搜索范围减半来找到目标值的位置。

具体来说,lower_bound函数的实现步骤如下:

初始化两个指针(或迭代器),一个指向区间的起始位置(first),另一个指向区间的结束位置(last)。
当first不等于last时,执行以下步骤:
计算中间位置mid = first + (last - first) / 2。注意这里使用(last - first) / 2而不是直接除以2,是为了避免在大数据集上发生整数溢出。
如果中间位置的值小于目标值(*mid < value),则将first更新为mid + 1,继续在右半部分搜索。
否则(中间位置的值大于或等于目标值),将last更新为mid,继续在左半部分或当前位置搜索。
返回first作为结果。此时,first指向的是第一个大于或等于目标值的元素的位置。如果找不到这样的元素,则返回last。
需要注意的是,由于二分查找算法的特性,lower_bound函数要求输入区间是有序的。如果输入区间无序,则结果不可预测。

4. 应用场景与扩展
lower_bound函数在多种场景下都非常有用,特别是当我们需要快速查找有序数据集中的特定元素时。以下是一些常见的应用场景:

在有序数组中查找元素:这是lower_bound函数最直接的应用场景。我们可以使用它来在有序数组中查找特定元素的位置。
在有序数组中查找插入位置:当我们需要在有序数组中插入一个新元素并保持数组有序时,可以使用lower_bound函数找到新元素的插入位置。这通常与std::vector的insert函数结合使用。
在有序集合中查找范围:我们可以使用lower_bound和upper_bound函数结合来查找有序集合中特定范围内的所有元素。这在处理统计数据或执行范围查询时非常有用。
自定义比较函数:除了使用默认的比较操作符外,我们还可以为lower_bound函数提供自定义的比较函数或Lambda表达式,以便根据特定的比较逻辑来查找元素。这在处理复杂数据类型或自定义排序规则时非常有用。
通过深入了解lower_bound函数的原理和实现细节,我们可以更好地利用这个强大的工具来解决各种实际问题。

lower_bound 是 C++ 标准库中的一个算法,它在一个有序序列中查找第一个不小于(即大于或等于)给定值的元素,并返回该元素的迭代器。如果序列中所有元素都小于给定值,则返回尾迭代器。

以下是使用 lower_bound 的五个案例:

案例 1:基本用法
cpp
#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::vector<int> v = {1, 2, 4, 4, 5, 6, 7};  
    int target = 4;  
      
    auto it = std::lower_bound(v.begin(), v.end(), target);  
      
    if (it != v.end()) {  
        std::cout << "First element not less than " << target << " is at index " << (it - v.begin()) << std::endl;  
    } else {  
        std::cout << target << " not found in the vector" << std::endl;  
    }  
      
    return 0;  
}
输出:

bash
First element not less than 4 is at index 2
案例 2:在自定义对象上使用 lower_bound
cpp
#include <iostream>  
#include <vector>  
#include <algorithm>  
  
struct Person {  
    std::string name;  
    int age;  
      
    bool operator<(const Person& other) const {  
        return age < other.age;  
    }  
};  
  
int main() {  
    std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};  
    int targetAge = 27;  
      
    auto it = std::lower_bound(people.begin(), people.end(), Person{"", targetAge},   
                               [](const Person& a, const Person& b) {  
                                   return a.age < b.age;  
                               });  
      
    if (it != people.end() && it->age == targetAge) {  
        std::cout << "Person with age " << targetAge << " found: " << it->name << std::endl;  
    } else {  
        std::cout << "No person with age " << targetAge << " found" << std::endl;  
    }  
      
    return 0;  
}
输出:

bash
No person with age 27 found
案例 3:在数组中使用 lower_bound
cpp
#include <iostream>  
#include <algorithm>  
  
int main() {  
    int arr[] = {1, 3, 5, 7, 9};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int target = 6;  
      
    int* result = std::lower_bound(arr, arr + n, target);  
      
    if (result != arr + n && *result == target) {  
        std::cout << "Element found at index " << (result - arr) << std::endl;  
    } else {  
        std::cout << "Element not found" << std::endl;  
    }  
      
    return 0;  
}
输出:

bash
Element not found
案例 4:处理重复元素
cpp
#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::vector<int> v = {1, 2, 3, 3, 3, 4, 5};  
    int target = 3;  
      
    auto lower = std::lower_bound(v.begin(), v.end(), target);  
    auto upper = std::upper_bound(v.begin(), v.end(), target);  
      
    std::cout << "Range of " << target << " in the vector: ["   
              << (lower - v.begin()) << ", " << (upper - v.begin() - 1) << "]" << std::endl;  
      
    return 0;  
}
输出:

bash
Range of 3 in the vector: [2, 4]

这篇关于lower_bound详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID:1. ​​useGeneratedKeys+keyProperty(推

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数

Linux系统性能检测命令详解

《Linux系统性能检测命令详解》本文介绍了Linux系统常用的监控命令(如top、vmstat、iostat、htop等)及其参数功能,涵盖进程状态、内存使用、磁盘I/O、系统负载等多维度资源监控,... 目录toppsuptimevmstatIOStatiotopslabtophtopdstatnmon

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Android ClassLoader加载机制详解

《AndroidClassLoader加载机制详解》Android的ClassLoader负责加载.dex文件,基于双亲委派模型,支持热修复和插件化,需注意类冲突、内存泄漏和兼容性问题,本文给大家介... 目录一、ClassLoader概述1.1 类加载的基本概念1.2 android与Java Class

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

SpringBoot线程池配置使用示例详解

《SpringBoot线程池配置使用示例详解》SpringBoot集成@Async注解,支持线程池参数配置(核心数、队列容量、拒绝策略等)及生命周期管理,结合监控与任务装饰器,提升异步处理效率与系统... 目录一、核心特性二、添加依赖三、参数详解四、配置线程池五、应用实践代码说明拒绝策略(Rejected

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

C#读写文本文件的多种方式详解

《C#读写文本文件的多种方式详解》这篇文章主要为大家详细介绍了C#中各种常用的文件读写方式,包括文本文件,二进制文件、CSV文件、JSON文件等,有需要的小伙伴可以参考一下... 目录一、文本文件读写1. 使用 File 类的静态方法2. 使用 StreamReader 和 StreamWriter二、二进

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v