lower_bound和upper_bound算法实现

冷不防 2021-10-23 13:46 230阅读 0赞

lower\_bound算法要求在已经按照非递减顺序排序的数组中找到第一个大于等于给定值key的那个数，其基本实现原理是二分查找，如下所示：

int lower_bound(vector<int> arr, int key) {
        int half;
        int len = arr.size();
        int mid;
        int first = 0;
        while (len > 0) {
            half = len >> 1;
            mid = first + half;
            //in the right part
            if (arr[mid] < key) {
                first = mid + 1;
                //因为first=mid+1,所以这里的len需要在减去half的基础之上再减去1
                len = len - half - 1;
            } else {
                //in the left part
                len = half;
            }
        }
        return first;
    }

upper\_bound函数要求在按照非递减顺序排好序的数组中找到第一个大于给定值key的那个数，其基本实现原理是二分查找，具体实现如下所示：

int upper_bound(vector<int> arr, int key) {
        int mid;
        int first = 0;
        int len = arr.size();
        int half;
        while (len > 0) {
            half = len >> 1;
            mid = half + first;
            if (arr[mid] > key) {
        //in the left part
                len = half;
            } else {
        //if arr[mid]<= key ,in the right part
                first = mid + 1;
                len = len - half - 1;
            }
        }
        return first;
    }

上述两种实现参考了stl中的实现方式，返回满足条件的值在数组中的下标。如果找不到满足条件的值，将会返回数组的大小，就像迭代器中的end一样，对应有效下标的下一个值。

转载于:https://www.cnblogs.com/zhoudayang/p/5679066.html

发表评论取消回复

表情：

评论列表（有 0 条评论，230人围观）

还没有评论，来说两句吧...

相关阅读

相关实现LowerBound方法的下界法算法

下界法是一种常用的算法技巧，用于在有序数组中查找某个元素的下界（LowerBound）。下界是指在有序数组中，大于或等于目标元素的最小索引值。下界法可以通过二分查找的方式高效地

偏执的太偏执、/ 2024年03月02日 08:54/ 0 赞/ 48 阅读

相关二分查找算法原理和实现

二分查找是一种比较高效的搜索算法，是一种可以在有序数组中搜索到特定元素的算法。例如，我们要在数组\{1,4,6,10,20\}中搜索4 1. 首先与数组的中间位置的

我会带着你远行/ 2023年06月13日 15:28/ 0 赞/ 14 阅读

相关查找算法的实现和比较

一直想比较一下查找算法，最近工作之余实现了一下算法，做了一下对比现在有一链表 static ArrayList \_serverList = new ArrayList(

我不是女神ヾ/ 2022年09月19日 05:24/ 0 赞/ 10 阅读

相关 AdaBoost算法和java实现

AdaBoost算法和java实现 -------------------- 算法描述输入：训练数据集![这里写图片描述][20150829093413536]

深藏阁楼爱情的钟/ 2022年08月03日 11:38/ 0 赞/ 234 阅读

相关 Java实现lowerBound及upperBound

Java中已经实现了BinarySearch，但没有lowerBound和upperBound，整理一下其实现原理。折半查找中，寻求中间元素的下标时，使用的是“ int

拼搏现实的明天。/ 2022年07月28日 04:25/ 0 赞/ 136 阅读

相关全排列算法原理和实现

`http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html` 本文为原创，如需转载，请注明作者和出处，谢

r囧r小猫/ 2022年05月15日 00:13/ 0 赞/ 188 阅读

相关经典排序算法实现和总结

算法分类非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。线性时间非比较类排序：不通过比

爱被打了一巴掌/ 2022年04月03日 08:27/ 0 赞/ 234 阅读

相关一致性hash算法和Java实现

一致性hash算法一、前言在大型web应用中，缓存可算是当今的一个标准开发配置了。在大规模的缓存应用中，应运而生了分布式缓存系统。在高并发（比如20W/S QP

r囧r小猫/ 2022年03月17日 10:44/ 0 赞/ 449 阅读

相关 KMeans++算法理论和实现

https://github.com/Sean16SYSU/MachineLearningImplement 简述在Kmeans当中，有两个限制定义在

缺乏、安全感/ 2022年02月24日 09:06/ 0 赞/ 281 阅读

相关 DBSCAN算法理论和Python实现

[https://github.com/Sean16SYSU/MachineLearningImplement][https_github.com_Sean16SYSU_

傷城~/ 2022年02月23日 02:48/ 0 赞/ 260 阅读