Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

lower_bound、upper_boundの基本的な使い方

どちらも二分探索を行う関数で、関数呼び出し時に探索したい値を指定する。

lower_bound

探索したい値以上が現れる最初の位置のイテレータを取得。
インデックスを取得したい場合は、取得したイテレータ - 探索したい領域の先頭すればよい。

例)
探索したい領域 : vector<int> v = {1, 2, 3, 4, 5}
探索したい値 : 3
結果 : 探索したい値以上なので、3の位置のイテレータが取得される。

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

int main(){
    vector<int> v = {1, 2, 3, 4, 5};
    auto it = lower_bound(v.begin(), v.end(), 3);

    int index = it - v.begin();

    // output
    //   index: 2
    //   value: 3
    cout << "index: " << index << endl;
    cout << "value: " << v[index] << endl;
    return 0;
}

探索したい値が見つからなかった場合。領域の最後のイテレータが返される(?)

    vector<int> v = {1, 2, 3, 4, 5};
    auto it = lower_bound(v.begin(), v.end(), 7);

    int index = it - v.begin();

    // output
    //   index: 5
    //   value: 0
    cout << "index: " << index << endl;
    cout << "value: " << v[index] << endl;
    return 0;

upper_bound

探索したい値より大きい値が現れる最初の位置のイテレータを取得。

例)
探索したい領域 : vector<int> v = {1, 2, 3, 4, 5}
探索したい値 : 3

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

int main(){
    vector<int> v = {1, 2, 3, 4, 5};
    auto it = upper_bound(v.begin(), v.end(), 3);

    int index = it - v.begin();

    // output
    //   index: 3
    //   value: 4
    cout << "index: " << index << endl;
    cout << "value: " << v[index] << endl;
    return 0;
}

探索したい値より大きい値なので、4の位置のイテレータが取得される。

kontotto
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away