STL源码剖析之【二分查找】

2024-09-07 18:38
文章标签 源码 剖析 二分 查找 stl

本文主要是介绍STL源码剖析之【二分查找】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

     ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中第一个大于val的位置。

     lower_bound和upper_bound如下图所示:

 

1:lower_bound的源码

template <class _ForwardIter, class _Tp, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,const _Tp& __val, _Distance*) 
{_Distance __len = 0;distance(__first, __last, __len);_Distance __half;_ForwardIter __middle;while (__len > 0) {__half = __len >> 1;__middle = __first;advance(__middle, __half);if (*__middle < __val) {__first = __middle;++__first;__len = __len - __half - 1;}else__len = __half;}return __first;
}

(将迭代器改掉后更容易懂)

int lower_bound(int *array, int size, int key)
{int first = 0, middle;int half, len;len = size;while(len > 0) {half = len >> 1;middle = first + half;if(array[middle] < key) {     first = middle + 1;          len = len-half-1;       //在右边子序列中查找}elselen = half;            //在左边子序列(包含middle)中查找}return first;
}

改成平时大家写的二分形式:(经过测试,和STL源码效果一样,在OJ平台测试过)

int Lower_bound(int *a , int n , int value)
{int left = 0;int right = n-1;while(left <= right){int mid = (left + right)/2;if(a[mid] < value){left = mid+1;}else right = mid -1;}return left;
}

2: upper_bound(已将迭代器改掉了)

源码:

int upper_bound(int *array, int size, int key)
{int first = 0, len = size-1;int half, middle;while(len > 0){half = len >> 1;middle = first + half;if(array[middle] > key)     //中位数大于key,在包含last的左半边序列中查找。len = half;else{first = middle + 1;    //中位数小于等于key,在右半边序列中查找。len = len - half - 1;}}return first;
}

改成平时大家写的二分形式:(经过测试,和STL源码效果一样,在OJ平台测试过)

int Lower_bound(int *a , int n , int value)
{int left = 0;int right = n-1;while(left <= right){int mid = (left + right)/2;if(a[mid] <= value){left = mid+1;}else right = mid -1;}return left;
}

3:binary_search()是基于lower_bound的,先找出lower_bound的位置,然后判断该位置是否是我们需要找的目标,返回对比结果


这篇关于STL源码剖析之【二分查找】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

Java汇编源码如何查看环境搭建

《Java汇编源码如何查看环境搭建》:本文主要介绍如何在IntelliJIDEA开发环境中搭建字节码和汇编环境,以便更好地进行代码调优和JVM学习,首先,介绍了如何配置IntelliJIDEA以方... 目录一、简介二、在IDEA开发环境中搭建汇编环境2.1 在IDEA中搭建字节码查看环境2.1.1 搭建步

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

Java ArrayList扩容机制 (源码解读)

结论:初始长度为10,若所需长度小于1.5倍原长度,则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1:数组默认长度         2:这是一个共享的空数组实例,用于明确创建长度为0时的ArrayList ,比如通过 new ArrayList<>(0),ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL