C++折半查找之lower-创新互联

C++ 折半查找之 lower_bound 和 upper_bound 1. lower_bound 1.1 基本用法

含义：满足下界的就 pass，找到第一个不满足下界的元素，即第一个 >= 下界 的元素， 返回其迭代器

专业成都网站建设公司，做排名好的好网站，排在同行前面，为您带来客户和效益!成都创新互联为您提供成都网站建设，五站合一网站设计制作，服务好的网站设计公司，成都网站建设、网站设计负责任的成都网站制作公司!

这里的下界 为 7, 所以是这样理解，凡是小于 7 的都是满足 下界，都会 pass，直到找到 >= 7 的元素，然后返回这个元素的迭代器。

vectorv = {1,4,5,2,3,6,8,12,9,7,11,10};

auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl;   // 8

注意这里返回的是 8 ，也就是第一个 >= 7 的元素， 而不是最小的 >= 7 的元素

所以 lower_bound 的含义是，返回序列中第一个 >= 下界的元素 的迭代器，元素 7 不是 第一个 >= 7 的元素

1.2 注意点

使用 lower_bound 时候 的注意点

• lower_bound 需要满足 所有元素 ”有序“, 但是这里的有序不是一定要 单调递增 或者 单调递减，而是序列中的 前部分 都是 小于 下界，后部分 都是 大于等于 下界，但是 前部分 和 后部分 各自内部 是 可以 乱序 的。

参考 C++ lower_bound()函数用法详解

下面验证这个点

vectorv = {1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 };  // size()=15, v[7]=13

auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl;   // 100

似乎这里按照往常 折半 的思路，应该第一个比较的元素是中间的元素 13 ，应该直接返回 13，因为 13 已经满足 大于等于下界了，但是按照 lower_bound() 的含义，必须是第一个 >= 下界的元素，所以 13 未必是 第一个，因此，可以认为此时

left指针=0，v[0]=1

right指针=7, v[7]=13

然后继续在 v[0]~v[7] 之间继续 折半 搜索下去

整个过程大概是这样，下界 = 7

查找范围	中间值	新范围
v[0]~v[14]	v[7]=13	v[0]~v[7]
v[0]~v[7]	v[3]=16	v[0]~v[3]
v[0]~v[3]	v[1]=2	v[2]~v[3]
v[2]~v[3]	v[2]=100	v[2]~v[2]

最终返回 v[2]=100 的迭代器

再次验证

vectorv = {4,3,1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 };

auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl;   // 100

1.3 错误使用 lower_bound 的情况

合理的序列：前部分< 下界，后部分 >= 下界

假如前部分是包含了 >= 下界 的元素，此时就不能使用 lower_bound() ，因为结果是错误的

vectorv = {101,4,3,1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 };

auto it = lower_bound(v.begin(), v.end(), 7);
cout<< *it<< endl;   // 100

所以 lower_bound 查找的范围必须满足

• lower_bound 需要满足 所有元素 ”有序“, 但是这里的有序不是一定要 单调递增 或者 单调递减 ，而是序列中的 前部分 都是 小于< 下界，后部分 都是 大于等于< 下界，但是 前部分 和 后部分 各自内部 是 可以 乱序 的。

1.4 自定义比较函数

lower_bound 支持 自定义的 比较规则

序列中的 前部分满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false

找到第 1 个返回 false 的元素

bool cmp(const int& e, const int& val)
{return e< val;  // val 始终等于 7
}


int main()
{//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 >= 7 的元素
	vectorv = {4,3,1,2,100,16,18,17,11,13,81,115,9,16,13,15,19 };

	auto it = lower_bound(v.begin(), v.end(), 7,cmp);
    // 等效 auto it = lower_bound(v.begin(), v.end(), 7);
	cout<< *it<< endl;   // 100

	return 0;
}

如上，cmp 的 **第二个参数 val **始终等于 7 ( lower_bound 中的 第 3 个参数 值 )，

• 凡是 满足 cmp 的元素值 ( 即cmp 返回 true )，认为都是满足< 下界的，都会 pass
• 凡是 cmp 返回 false的 ，就是 >= 下界，lower_bound 返回 序列 中 第一个 让 cmp 不成立的元素

注意，序列中的 前部分 应该是 满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false，即 前 T 后 F

否则可能会出问题

比如下面 2 种情况，前 F 后 T，恰好相反

bool cmp(const int& e, const int& val)
{return e< val;
}

//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 >= 15 的元素
vectorv = {100,16,18,17,11,13,10,5,1,2,3,5,6,4,3,1,2 };

auto it = lower_bound(v.begin(), v.end(), 15,cmp);
if (it == v.end())
    cout<< "未找到满足条件的元素"<< endl;
else
    cout<< *it<< endl; 
// 输出 未找到满足条件的元素

中间元素 v[8]=1, 导致后续在 v[9]~v[16] 搜索，而 v[9]~v[16] 不存在 >= val 的元素

没有找到 v[0]=100

bool cmp(const int& e, const int& val)
{return e< val;
}

//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 >= 15 的元素
vectorv = {100,16,18,17,21,23,19,51,81,32,32,5,6,4,3,1,2 };

auto it = lower_bound(v.begin(), v.end(), 15,cmp);
if (it == v.end())
    cout<< "未找到满足条件的元素"<< endl;
else
    cout<< *it<< endl;   
// 输出 100

中间元素 v[8]=81, 导致后续在 v[0]~v[8] 搜素，能够找到 v[0]=100

主要还是看第一次 中间的 那个元素

所以，最好还是满足

• 序列中的 前部分满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false

再次测试

让 序列中的 前部分满足 cmp (即 cmp 返回 true)，后部分 不满足 cmp， 返回 false

lower_bound 返回第一个 让 cmp 返回 false 的元素的 迭代器

测试1第 1 个< 20 的元素

bool cmp(const int& e, const int& val)
{return e >= val;
}


int main()
{//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个< 20 的元素
	vectorv = {31,88,41,25,20,22,20,8,12,9,7,11,10};

	auto it = lower_bound(v.begin(), v.end(), 20,cmp);
	if (it == v.end())
		cout<< "未找到满足条件的元素"<< endl;
	else
		cout<< *it<< endl;   // 8

	return 0;
}

测试2第 1 个 无法 被 5 整除 的元素

bool cmp(const int& e, const int& val)
{return (e % val)==0;
}


int main()
{//找到一个 让 cmp 返回 false 的元素的下标, 即 第 1 个 无法 被 5 整除 的元素
	vectorv = {30,80,40,20,20,25,35,80,12,9,7,11,5};

	auto it = lower_bound(v.begin(), v.end(), 5,cmp);
	if (it == v.end())
		cout<< "未找到满足条件的元素"<< endl;
	else
		cout<< *it<< endl;   // 12

	return 0;
}

测试3当然也可以使用 lambda 表达式

int main()
{//找到一个 让 lambda 返回 false 的元素的下标, 即 第 1 个 无法被 5 整除 的元素
	vectorv = {30,80,40,20,20,25,35,80,12,9,7,11,5};

	//auto it = lower_bound(v.begin(), v.end(), 5,cmp);

	auto it = lower_bound(v.begin(), v.end(), 5, [](const int& e, const int& val) {return (e % val) == 0;});
	if (it == v.end())
		cout<< "未找到满足条件的元素"<< endl;
	else
		cout<< *it<< endl;   // 12

	return 0;
}

2. upper_bound

在 windows vs2019 环境下, upper_bound 需要 #include ，但是 lower_bound 不需要

2.1 基本用法

不使用自定义函数的情况下

测试1lower_bound 返回 第一个 >= 下界 的元素, upper_bound 返回 第一个 >下界 的元素

vectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };

// 找到 第一个 >= 9 的元素
auto it1 = lower_bound(v.begin(), v.end(), 9);

if (it1 == v.end())
    cout<< "lower_bound 未找到满足条件的元素"<< endl;
else
    cout<< *it1<< endl;   // 9

// 找到 第一个 >9 的元素
auto it2 = upper_bound(v.begin(), v.end(), 9);

if (it2 == v.end())
    cout<< "upper_bound 未找到满足条件的元素"<< endl;
else
    cout<< *it2<< endl;   // 100

测试2lower_bound 返回第一个 >= 下界 的元素, upper_bound 返回第一个 >下界 的元素

int main()
{vectorv = {4,3,1,2,9 };
    
    // 找到 第一个 >= 9 的元素
	auto it1 = lower_bound(v.begin(), v.end(), 9);

	if (it1 == v.end())
		cout<< "lower_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it1<< endl;   // 9
    
    // 找到 第一个 >9 的元素
	auto it2 = upper_bound(v.begin(), v.end(), 9);
	
    
	if (it2 == v.end())
		cout<< "upper_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it2<< endl;   
	// upper_bound 未找到满足条件的元素
	return 0;
}

2.2 自定义比较函数

注意，upper_bound 中 cmp 的 **第1个参数 val **始终等于 9 ( upper_bound 中的 第 3 个参数 值 )，

• 序列中的 前部分不满足 cmp (即 cmp 返回 false )，后部分 满足 cmp， 返回 true

返回第一个 满足 cmp (返回true) 的 元素 的迭代器

测试3找到第一个大于 9 的元素，返回其迭代器

bool cmp2(const int& val, const int& e)
{return valvectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };
	
    // 找到第一个 >9 的元素, 即 a[5]=100
	auto it2 = upper_bound(v.begin(), v.end(), 9,cmp2);

	if (it2 == v.end())
		cout<< "upper_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it2<< endl;   // 100

	return 0;
}

测试4找到第一个能被 5 整除 的元素，返回其迭代器

bool cmp3(const int& val, const int& e)
{return (e % val) == 0;
}

int main()
{vectorv = {4,19,26,34,17,29,40,10,15,30,20 };
	auto it2 = upper_bound(v.begin(), v.end(), 5,cmp3);

	if (it2 == v.end())
		cout<< "upper_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it2<< endl;   // 40

	return 0;
}

2.3 upper_bound 和 lower_bound 的区别

auto it1 = lower_bound(v.begin(), v.end(), val,cmp1);
auto it2 = upper_bound(v.begin(), v.end(), val,cmp2);

	lower_bound	upper_bound
无自定义比较函数	返回第一个 >= 下界 的元素	返回第一个 >下界 的元素
使用自定义比较函数	返回第一个 false 的元素 val 是 自定义函数 中的第 2 个参数 e< val	返回第一个 true 的元素 val 是自定义函数中的 第 1 个参数 val< e
	序列的前部分满足 cmp (返回 true) 后部分不满足 cmp (返回 false) 找到第 1 个 false 的元素	序列的前部分不满足 cmp (返回 false) 后部分满足 cmp (返回 true) 找到第 1 个 true 的元素

关于 val 在 lower_bound 的 cmp 中 是第 2 个参数 ，在 upper_bound 的 cmp 中 是 第 1 个参数

简单的记忆：比较的时候都是用 小于<

lower 就是 小于 ，即小于 val , e< val，所以 val 是 第 2 个参数

upper 就是 大于 ，即大于 val , val< e，所以 val 是 第 1 个参数

测试4lower_bound 和 upper_bound 都是用 自定义函数

bool cmp1(const int& e, const int& val)
{return e< val;
}

bool cmp2(const int& val, const int& e)
{return val< e;
}

int main()
{vectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };
	auto it1 = lower_bound(v.begin(), v.end(), 9,cmp1);
	
    // 第一个让 cmp1 返回 false 的元素, 即第一个 >= 9 的元素 
	if (it1 == v.end())
		cout<< "lower_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it1<< endl;   // 9

	cout<< endl<< endl<< endl;

    // 第一个让 cmp2 返回 true 的元素, 即第一个 >9 的元素 
	auto it2 = upper_bound(v.begin(), v.end(), 9,cmp2);

	if (it2 == v.end())
		cout<< "upper_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it2<< endl;   // 100

	return 0;
}

upper_bound 将 cmp 中改成 >= ， 即得到和 lower_bound 一样的结果

bool cmp2(const int& val, const int& e)
{//cout<< val<< '\t'<< e<< endl;
	return val<= e;
}


int main()
{vectorv = {4,3,1,2,9,100,16,18,17,11,13,81,115,9,16,13,15,19 };
    
	// 第一个让 cmp2 返回 true 的元素, 即第一个 >= 9 的元素
	auto it2 = upper_bound(v.begin(), v.end(), 9,cmp2);

	if (it2 == v.end())
		cout<< "upper_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it2<< endl;   // 9

	return 0;
}

测试5lower_bound 和 upper_bound 都找到第一个 能被 5 整除 的元素，返回其迭代器

bool cmp1(const int& e, const int& val)
{return (e % val) != 0;
}

bool cmp2(const int& val, const int& e)
{return (e % val) == 0;
}



int main()
{vectorv = {4,19,26,34,17,29,40,10,15,30,20 };
    
    // 寻找第 1 个让 cmp1 为 false的元素, 即  第 1 个 5 的倍数
    // 非 5 的倍数,cmp1 为true, 直接 pass
    // 遇到第一个 5 的倍数, cmp1 为 false， 返回该元素
	auto it1 = lower_bound(v.begin(), v.end(), 5, cmp1);


	if (it1 == v.end())
		cout<< "lower_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it1<< endl;   // 40

	cout<< endl<< endl<< endl;
	
    // 寻找让 cmp2 返回 true 的第 1 个元素的迭代器, 也就是找到 第 1 个 5 的倍数
	auto it2 = upper_bound(v.begin(), v.end(), 5,cmp2);

	if (it2 == v.end())
		cout<< "upper_bound 未找到满足条件的元素"<< endl;
	else
		cout<< *it2<< endl;   // 40

	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

新闻名称：C++折半查找之lower-创新互联
网页URL：http://dzwzjz.com/article/djcces.html