STL 中，在 <algorithm> 頭文件里提供了兩個(gè)利用二分查找的方法在一個(gè)排好序的數(shù)組中進(jìn)行查找。

在一個(gè)從小到大的排好序的數(shù)組中：

• lower_bound(begin,end,num)：從數(shù)組的 begin 位置到 end-1 位置二分查找第一個(gè)大于等于 num 的數(shù)字，找到返回該數(shù)字的地址，不存在則返回 end
• upper_bound( begin,end,num)：從數(shù)組的 begin 位置到 end-1 位置二分查找第一個(gè)大于 num 的數(shù)字，找到返回該數(shù)字的地址，不存在則返回 end

而在一個(gè)從大到小的排好序的數(shù)組中：

• lower_bound( begin,end,num,greater<type>() )：從數(shù)組的 begin 位置到 end-1 位置二分查找第一個(gè)小于等于 num 的數(shù)字，找到返回該數(shù)字的地址，不存在則返回 end
• upper_bound( begin,end,num,greater<type>() )：從數(shù)組的 begin 位置到 end-1 位置二分查找第一個(gè)小于 num 的數(shù)字，找到返回該數(shù)字的地址，不存在則返回 end。

可以通過(guò)這兩個(gè)方法返回的地址減去起始地址 begin，即可得到數(shù)字在數(shù)組中的下標(biāo)。

int cmp(int a,int b){return a>b; } int num[5]={1,4,6,9,8}; int pos;sort(num,num+5);//按從小到大 pos=lower_bound(num,num+5,7)-num;//返回?cái)?shù)組中第一個(gè)大于或等于7的值 pos=upper_bound(num,num+5,7)-num;//返回?cái)?shù)組中第一個(gè)大于7的值sort(num,num+6,cmp);//按從大到小 pos=lower_bound(num,num+5,7,greater<int>())-num;//返回?cái)?shù)組中第一個(gè)小于或等于7的值 pos=upper_bound(num,num+5,7,greater<int>())-num;//返回?cái)?shù)組中第一個(gè)小于7的值

?

總結(jié)

以上是生活随笔為你收集整理的C++ 语言基础 —— STL —— 算法 —— 二分查找算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。