lower_bound和upper_bound算法实现

冷不防 2021-10-23 13:46 197阅读 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 条评论，197人围观）

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

相关阅读

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

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

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

相关 kmeans算法python实现三类_K-Means 算法总结和 Python 实现

在聚类算法中，我们给定训练集 $\{x\{(1)\},...,x\{(m)\}\}$ (醉了，简书的 Markdown 平台不支持数学公式的解析 o(≧口≦)o，可参考我另外的

叁歲伎倆/ 2023年01月09日 01:16/ 0 赞/ 108 阅读

相关缓存基础----LRU算法和FIFO算法的Java实现

Java里面实现LRU缓存算法的通常有两种选择，一种是自己设计数据结构：链表+HashMap（链表用来表示位置，哈希表用来存储和查找），另一种是使用Java中的LinkedHa

小灰灰/ 2022年10月12日 01:19/ 0 赞/ 111 阅读

相关 AdaBoost算法和java实现

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

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

相关 Java实现lowerBound及upperBound

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关 DBSCAN算法理论和Python实现

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

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