資料結構介紹 - Upper_bound & Lower_bound - by Peter Wang

tags: 演算法介紹

用途：針對「已經排序」的資料進行 binary search。

lower_bound：

找出vector中「大於或等於」val的「最小值」的位置：
auto it = lower_bound(v.begin(), v.end(), val);

upper_bound：

找出vector中「大於」val的「最小值」的位置：
auto it = upper_bound(v.begin(), v.end(), val);

程式範例

以下為sort輸入的數字，並且找出對應find的upper_bound位置。（lower_bound的用法與upper_bound相同）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while(cin>>n){
        vector <int> up;
        for(int i=0;i<n;i++){
            int a;
            cin>>a;
            up.push_back(a);
        }
        sort(up.begin(),up.end());
        int find;
        cin>>find;
        int ans=upper_bound(up.begin(),up.end(),find)-up.begin();//減去begin()是為了取得vector中的位置
        cout<< ans <<endl;
    }
}

補充介紹 set 的 lower_bound & upper_bound

用法與vector類似但有些必須注意的細節，以下為APCS 2021 1月第三題 切割費用 的範例。

set 的 upper_bound當中是直接放 value，這是與vector最不一樣的地方。（lower_bound的用法與upper_bound相同）

程式範例

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int n,l;
vector <pair<int,int>> knife;

bool cmp(pair<int,int> a,pair<int,int> b){
  return a.second<b.second;
}

int main() {
  while(cin>>n>>l){
    for(int i=0;i<n;i++){
      int a,b;
      cin>>a>>b;
      knife.push_back({a,b});
    }
    sort(knife.begin(),knife.end(),cmp);
    long long ans=0;
    set <int> count;
    count.insert(0);
    count.insert(l);
    for(int i=0;i<n;i++){
      count.insert(knife[i].first);
      auto it=count.upper_bound(knife[i].first);
      it--;
      ans += *next(it)-*prev(it);
    }
    cout<<ans<<endl;
  }
}

備註

Peter Wang
Thu, Aug 12, 2021 10:15 PM