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

含義：滿足下界的就 pass，找到第一個(gè)不滿足下界的元素，即第一個(gè) >= 下界 的元素， 返回其迭代器

專業(yè)成都網(wǎng)站建設(shè)公司，做排名好的好網(wǎng)站，排在同行前面，為您帶來客戶和效益!成都創(chuàng)新互聯(lián)為您提供成都網(wǎng)站建設(shè)，五站合一網(wǎng)站設(shè)計(jì)制作，服務(wù)好的網(wǎng)站設(shè)計(jì)公司，成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)負(fù)責(zé)任的成都網(wǎng)站制作公司!

這里的下界 為 7, 所以是這樣理解，凡是小于 7 的都是滿足 下界，都會(huì) pass，直到找到 >= 7 的元素，然后返回這個(gè)元素的迭代器。

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 ，也就是第一個(gè) >= 7 的元素， 而不是最小的 >= 7 的元素

所以 lower_bound 的含義是，返回序列中第一個(gè) >= 下界的元素 的迭代器，元素 7 不是 第一個(gè) >= 7 的元素

1.2 注意點(diǎn)

使用 lower_bound 時(shí)候 的注意點(diǎn)

• lower_bound 需要滿足 所有元素 ”有序“, 但是這里的有序不是一定要 單調(diào)遞增 或者 單調(diào)遞減，而是序列中的 前部分 都是 小于 下界，后部分 都是 大于等于 下界，但是 前部分 和 后部分 各自內(nèi)部 是 可以 亂序 的。

參考 C++ lower_bound()函數(shù)用法詳解

下面驗(yàn)證這個(gè)點(diǎn)

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

似乎這里按照往常 折半 的思路，應(yīng)該第一個(gè)比較的元素是中間的元素 13 ，應(yīng)該直接返回 13，因?yàn)?13 已經(jīng)滿足 大于等于下界了，但是按照 lower_bound() 的含義，必須是第一個(gè) >= 下界的元素，所以 13 未必是 第一個(gè)，因此，可以認(rèn)為此時(shí)

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

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

然后繼續(xù)在 v[0]~v[7] 之間繼續(xù) 折半 搜索下去

整個(gè)過程大概是這樣，下界 = 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 的迭代器

再次驗(yàn)證

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 錯(cuò)誤使用 lower_bound 的情況

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

假如前部分是包含了 >= 下界 的元素，此時(shí)就不能使用 lower_bound() ，因?yàn)榻Y(jié)果是錯(cuò)誤的

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 需要滿足 所有元素 ”有序“, 但是這里的有序不是一定要 單調(diào)遞增 或者 單調(diào)遞減 ，而是序列中的 前部分 都是 小于< 下界，后部分 都是 大于等于< 下界，但是 前部分 和 后部分 各自內(nèi)部 是 可以 亂序 的。

1.4 自定義比較函數(shù)

lower_bound 支持 自定義的 比較規(guī)則

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

找到第 1 個(gè)返回 false 的元素

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


int main()
{//找到一個(gè) 讓 cmp 返回 false 的元素的下標(biāo), 即 第 1 個(gè) >= 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 的 **第二個(gè)參數(shù) val **始終等于 7 ( lower_bound 中的 第 3 個(gè)參數(shù) 值 )，

• 凡是 滿足 cmp 的元素值 ( 即cmp 返回 true )，認(rèn)為都是滿足< 下界的，都會(huì) pass
• 凡是 cmp 返回 false的 ，就是 >= 下界，lower_bound 返回 序列 中 第一個(gè) 讓 cmp 不成立的元素

注意，序列中的 前部分 應(yīng)該是 滿足 cmp (即 cmp 返回 true)，后部分 不滿足 cmp， 返回 false，即 前 T 后 F

否則可能會(huì)出問題

比如下面 2 種情況，前 F 后 T，恰好相反

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

//找到一個(gè) 讓 cmp 返回 false 的元素的下標(biāo), 即 第 1 個(gè) >= 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, 導(dǎo)致后續(xù)在 v[9]~v[16] 搜索，而 v[9]~v[16] 不存在 >= val 的元素

沒有找到 v[0]=100

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

//找到一個(gè) 讓 cmp 返回 false 的元素的下標(biāo), 即 第 1 個(gè) >= 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, 導(dǎo)致后續(xù)在 v[0]~v[8] 搜素，能夠找到 v[0]=100

主要還是看第一次 中間的 那個(gè)元素

所以，最好還是滿足

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

再次測(cè)試

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

lower_bound 返回第一個(gè) 讓 cmp 返回 false 的元素的 迭代器

測(cè)試1第 1 個(gè)< 20 的元素

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


int main()
{//找到一個(gè) 讓 cmp 返回 false 的元素的下標(biāo), 即 第 1 個(gè)< 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;
}

測(cè)試2第 1 個(gè) 無法 被 5 整除 的元素

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


int main()
{//找到一個(gè) 讓 cmp 返回 false 的元素的下標(biāo), 即 第 1 個(gè) 無法 被 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;
}

測(cè)試3當(dāng)然也可以使用 lambda 表達(dá)式

int main()
{//找到一個(gè) 讓 lambda 返回 false 的元素的下標(biāo), 即 第 1 個(gè) 無法被 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 環(huán)境下, upper_bound 需要 #include ，但是 lower_bound 不需要

2.1 基本用法

不使用自定義函數(shù)的情況下

測(cè)試1lower_bound 返回 第一個(gè) >= 下界 的元素, upper_bound 返回 第一個(gè) >下界 的元素

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

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

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

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

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

測(cè)試2lower_bound 返回第一個(gè) >= 下界 的元素, upper_bound 返回第一個(gè) >下界 的元素

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

	if (it1 == v.end())
		cout<< "lower_bound 未找到滿足條件的元素"<< endl;
	else
		cout<< *it1<< endl;   // 9
    
    // 找到 第一個(gè) >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 自定義比較函數(shù)

注意，upper_bound 中 cmp 的 **第1個(gè)參數(shù) val **始終等于 9 ( upper_bound 中的 第 3 個(gè)參數(shù) 值 )，

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

返回第一個(gè) 滿足 cmp (返回true) 的 元素 的迭代器

測(cè)試3找到第一個(gè)大于 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 };
	
    // 找到第一個(gè) >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;
}

測(cè)試4找到第一個(gè)能被 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 的區(qū)別

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

	lower_bound	upper_bound
無自定義比較函數(shù)	返回第一個(gè) >= 下界 的元素	返回第一個(gè) >下界 的元素
使用自定義比較函數(shù)	返回第一個(gè) false 的元素 val 是 自定義函數(shù) 中的第 2 個(gè)參數(shù) e< val	返回第一個(gè) true 的元素 val 是自定義函數(shù)中的 第 1 個(gè)參數(shù) val< e
	序列的前部分滿足 cmp (返回 true) 后部分不滿足 cmp (返回 false) 找到第 1 個(gè) false 的元素	序列的前部分不滿足 cmp (返回 false) 后部分滿足 cmp (返回 true) 找到第 1 個(gè) true 的元素

關(guān)于 val 在 lower_bound 的 cmp 中 是第 2 個(gè)參數(shù) ，在 upper_bound 的 cmp 中 是 第 1 個(gè)參數(shù)

簡單的記憶：比較的時(shí)候都是用 小于<

lower 就是 小于 ，即小于 val , e< val，所以 val 是 第 2 個(gè)參數(shù)

upper 就是 大于 ，即大于 val , val< e，所以 val 是 第 1 個(gè)參數(shù)

測(cè)試4lower_bound 和 upper_bound 都是用 自定義函數(shù)

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);
	
    // 第一個(gè)讓 cmp1 返回 false 的元素, 即第一個(gè) >= 9 的元素 
	if (it1 == v.end())
		cout<< "lower_bound 未找到滿足條件的元素"<< endl;
	else
		cout<< *it1<< endl;   // 9

	cout<< endl<< endl<< endl;

    // 第一個(gè)讓 cmp2 返回 true 的元素, 即第一個(gè) >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 一樣的結(jié)果

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 };
    
	// 第一個(gè)讓 cmp2 返回 true 的元素, 即第一個(gè) >= 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;
}

測(cè)試5lower_bound 和 upper_bound 都找到第一個(gè) 能被 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 個(gè)讓 cmp1 為 false的元素, 即  第 1 個(gè) 5 的倍數(shù)
    // 非 5 的倍數(shù),cmp1 為true, 直接 pass
    // 遇到第一個(gè) 5 的倍數(shù), 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 個(gè)元素的迭代器, 也就是找到 第 1 個(gè) 5 的倍數(shù)
	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;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：C++折半查找之lower-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://weahome.cn/article/djcces.html