lower-創(chuàng)新互聯(lián)

文章目錄

- 1.lower_bound()/upper_bound()函數(shù)簡單介紹
- 2.lower_bound()/upper_bound()函數(shù)分析
- 3.lower_bound()/upper_bound()運行展示

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

?1.1 lower_bound() 用于二分查找區(qū)間內(nèi)第一個大于等于某值(>= x) 的迭代器位置
?1.2 upper_bound() 用于二分查找區(qū)間內(nèi)第一個大于某值(>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ù)前兩個參數(shù)分別是已被排序的序列的起始迭代器位置和結(jié)束迭代器位置，將要被查詢的范圍為[ first, last )，是一個左閉右開區(qū)間的范圍，第三個參數(shù)則是需要搜尋的元素的值。最后返回查詢成功的迭代器的位置。

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

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)細節(jié)注意
?A. 搜索的序列必須是已經(jīng)按照一定規(guī)則進行過排序的有序序列
?因為之前我們就介紹了這個函數(shù)是二分進行搜索位置的，所以必須保證其順序必須是有序的才可以，否則會亂套的，之后也可以運行展示以下如果不是有序的序列會出現(xiàn)的錯誤。
?B. 搜索的序列本身必須可以傳入迭代器參數(shù)
?因為這個函數(shù)需要傳入的參數(shù)就是迭代器的位置，所以如果對于本身沒有迭代器參數(shù)的序列是無法使用的，例如 queue容器是無法使用的(本身沒有迭代器成員函數(shù))，對于一般數(shù)組，vector容器，deque容器，set容器等(本身有迭代器函數(shù))都可以直接使用
?C. 搜索的序列當中若無合法答案返回 last 迭代器位置
?我們搜索的序列是[ fitst, last ]，當其中沒有我們想要的結(jié)果則會返回last迭代器的位置我們也可以借此確認是否真的可以成功搜索到合法結(jié)果。

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

3.lower_bound()/upper_bound()運行展示

?3.1 函數(shù)正常使用展示
? lower_bound() 找到第一個 >= x 的合法位置
? upper_bound() 找到第一個 >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第一個 >= 3 元素的大小為:  元素位置為：  "<< endl;
    cout<< * lower_bound(a, a + 7, 3)<< "\t";
    cout<< lower_bound(a, a + 7, 3) - a<< endl;
    cout<< "第一個 >3 元素的大小為:  元素位置為：  "<< endl;
    cout<< * upper_bound(a, a + 7, 3)<< "\t";
    cout<< upper_bound(a, a + 7, 3) - a<< endl;
}

在這里插入圖片描述

?3.2 函數(shù)細節(jié)1——搜索之前必須是有序序列
?我們設(shè)計一個沒有排序的隊列嘗試一下，也可以看看其內(nèi)部的搜索順序是二分查找的一個順序，我們可以看看結(jié)果。
? 這個序列第一個二分查找的元素就是9，然后查找 2 不合法，然后 1 9 中會將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第一個 >= 3 元素的大小為:  元素位置為：  "<< endl;
    cout<< * lower_bound(a, a + 7, 3)<< "\t";
    cout<< lower_bound(a, a + 7, 3) - a<< endl;

}

在這里插入圖片描述

?3.3 函數(shù)細節(jié)2——搜索對象必須是可以傳入迭代器參數(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<< "第一個 >= 3 的元素位置為: "<< endl;
    cout<< lower_bound(v.begin(), v.end(), 3) - v.begin()<< endl;
    cout<< "第一個 >= 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<< "第一個 >= 2 的數(shù)字為"<< endl;
    cout<< * lower_bound(s.begin(), s.end(), 2)<< endl;

}

在這里插入圖片描述

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

#include#include
#includeusing namespace std;
typedef long long LL;
int main(){int a[4] = {1, 2, 3, 4};
    cout<< "找到第一個 >= 5 的元素的大小"<< endl;
    cout<<  * lower_bound(a, a + 4, 5)<< endl;
    cout<< "找到第一個 >= 5 的元素的相對位置"<< 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海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章標題：lower-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://muchs.cn/article38/dphhpp.html

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

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

猜你還喜歡下面的內(nèi)容