文章目錄

• • 1.lower_bound()/upper_bound()函數(shù)簡(jiǎn)單介紹
  • 2.lower_bound()/upper_bound()函數(shù)分析
  • 3.lower_bound()/upper_bound()運(yùn)行展示

在瑪曲等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作定制網(wǎng)站制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,全網(wǎng)營銷推廣,外貿(mào)網(wǎng)站建設(shè),瑪曲網(wǎng)站建設(shè)費(fèi)用合理。1.lower_bound()/upper_bound()函數(shù)簡(jiǎn)單介紹

?1.1 lower_bound() 用于二分查找區(qū)間內(nèi)第一個(gè) 大于等于某值(>= x) 的迭代器位置
?1.2 upper_bound() 用于二分查找區(qū)間內(nèi)第一個(gè) 大于某值(>x) 的迭代器位置

2.lower_bound()/upper_bound()函數(shù)分析

?2.1 函數(shù)參數(shù)分析
?ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
?ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
?函數(shù)前兩個(gè)參數(shù)分別是已被排序的序列的起始迭代器位置和結(jié)束迭代器位置，將要被查詢的范圍為[ first, last )，是一個(gè)左閉右開區(qū)間的范圍，第三個(gè)參數(shù)則是需要搜尋的元素的值。最后返回查詢成功的迭代器的位置。

?2.2 函數(shù)內(nèi)部原理實(shí)現(xiàn)分析
?使用lower_bound()進(jìn)行一個(gè)簡(jiǎn)單的介紹，其實(shí)可以發(fā)現(xiàn)這個(gè)函數(shù)底層實(shí)現(xiàn)的一個(gè)邏輯就是二分查找

ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{ForwardIterator it;
  iterator_traits::difference_type count, step;
  count = distance(first,last);
  while (count>0) // 底層邏輯就是二分查找
  {it = first; step=count/2; advance (it,step);  // 每次獲取區(qū)間范圍的一半
    if (*it 
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

?2.3 函數(shù)相關(guān)細(xì)節(jié)注意
?A. 搜索的序列必須是已經(jīng)按照一定規(guī)則進(jìn)行過排序的有序序列
?因?yàn)橹拔覀兙徒榻B了這個(gè)函數(shù)是二分進(jìn)行搜索位置的，所以必須保證其順序必須是有序的才可以，否則會(huì)亂套的，之后也可以運(yùn)行展示以下如果不是有序的序列會(huì)出現(xiàn)的錯(cuò)誤。
?B. 搜索的序列本身必須可以傳入迭代器參數(shù)
?因?yàn)檫@個(gè)函數(shù)需要傳入的參數(shù)就是迭代器的位置，所以如果對(duì)于本身沒有迭代器參數(shù)的序列是無法使用的，例如 queue容器是無法使用的(本身沒有迭代器成員函數(shù))，對(duì)于一般數(shù)組，vector容器，deque容器，set容器等(本身有迭代器函數(shù))都可以直接使用
?C. 搜索的序列當(dāng)中若無合法答案返回 last 迭代器位置
?我們搜索的序列是[ fitst, last ]，當(dāng)其中沒有我們想要的結(jié)果則會(huì)返回last迭代器的位置我們也可以借此確認(rèn)是否真的可以成功搜索到合法結(jié)果。

?2.4: 函數(shù)頭文件 algorithm庫

3.lower_bound()/upper_bound()運(yùn)行展示

?3.1 函數(shù)正常使用展示
? lower_bound() 找到第一個(gè) >= x 的合法位置
? upper_bound() 找到第一個(gè) >x 的合法位置

#include#include
using namespace std;
typedef long long LL;
int main(){int a[7] = {0, 1, 3, 5, 8, 10, 16};
    for(int i = 0; i< 7; i ++ ) cout<< a[i]<< ' ';
    cout<< "\n第一個(gè) >= 3 元素的大小為:  元素位置為：  "<< endl;
    cout<< * lower_bound(a, a + 7, 3)<< "\t";
    cout<< lower_bound(a, a + 7, 3) - a<< endl;
    cout<< "第一個(gè) >3 元素的大小為:  元素位置為：  "<< endl;
    cout<< * upper_bound(a, a + 7, 3)<< "\t";
    cout<< upper_bound(a, a + 7, 3) - a<< endl;
}

?3.2 函數(shù)細(xì)節(jié)1——搜索之前必須是有序序列
?我們?cè)O(shè)計(jì)一個(gè)沒有排序的隊(duì)列嘗試一下，也可以看看其內(nèi)部的搜索順序是二分查找的一個(gè)順序，我們可以看看結(jié)果。
? 這個(gè)序列第一個(gè)二分查找的元素就是9，然后查找 2 不合法，然后 1 9 中會(huì)將9作為結(jié)果輸出

#include#include
using namespace std;
typedef long long LL;
int main(){int a[7] = {10, 2, 1, 9, 8, 2, 16};
    for(int i = 0; i< 7; i ++ ) cout<< a[i]<< ' ';
    cout<< "\n第一個(gè) >= 3 元素的大小為:  元素位置為：  "<< endl;
    cout<< * lower_bound(a, a + 7, 3)<< "\t";
    cout<< lower_bound(a, a + 7, 3) - a<< endl;

}

?3.3 函數(shù)細(xì)節(jié)2——搜索對(duì)象必須是可以傳入迭代器參數(shù)的序列
?沒有迭代器成員函數(shù)的容器是無法使用的例如 queue ， 其他迭代器都可以正常使用例如vector, set等
?常用的一般就是 vector容器， 也可以用 vector容器和set容器, deque容器 等(提醒：set容器本身內(nèi)部就是有序)
?vector容器

#include#include
#includeusing namespace std;
typedef long long LL;
int main(){vectorv;
    v.push_back(4), v.push_back(8), v.push_back(1), v.push_back(2), v.push_back(6);
    sort(v.begin(), v.end());
    cout<< "第一個(gè) >= 3 的元素位置為: "<< endl;
    cout<< lower_bound(v.begin(), v.end(), 3) - v.begin()<< endl;
    cout<< "第一個(gè) >= 3 的元素大小為: "<< endl;
    cout<< *lower_bound(v.begin(), v.end(), 3)<< endl;
}

?set容器本身內(nèi)部即有序(不需要排序操作)

#include#include
#includeusing namespace std;
typedef long long LL;
int main(){sets;
    s.insert(4), s.insert(2), s.insert(1), s.insert(5), s.insert(3);
    set::iterator it = s.begin();
    for(; it != s.end(); it ++ ){cout<< * it<< ' ';
    }
    cout<< '\n';
    cout<< "第一個(gè) >= 2 的數(shù)字為"<< endl;
    cout<< * lower_bound(s.begin(), s.end(), 2)<< endl;

}

?3.4 函數(shù)細(xì)節(jié)3——若無法搜索到合法答案返回末尾迭代器

#include#include
#includeusing namespace std;
typedef long long LL;
int main(){int a[4] = {1, 2, 3, 4};
    cout<< "找到第一個(gè) >= 5 的元素的大小"<< endl;
    cout<<  * lower_bound(a, a + 4, 5)<< endl;
    cout<< "找到第一個(gè) >= 5 的元素的相對(duì)位置"<< endl;
    cout<<  lower_bound(a, a + 4, 5) - a<< endl;
    if(lower_bound(a, a + 4, 5) == a + 4){cout<< "沒有正確的結(jié)果, 返回元素末尾[last]的位置"<< endl;
    
}

你是否還在尋找穩(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)題：lower-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://jinyejixie.com/article38/dphhpp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、面包屑導(dǎo)航、網(wǎng)站營銷、App設(shè)計(jì)、標(biāo)簽優(yōu)化、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)