Реализация lower_bound () и upper_bound () в массиве пар в C ++

Опубликовано: 22 Января, 2022

В этой статье мы обсудим реализацию lower_bound () и upper_bound () в массиве пар.

  • lower_bound (): возвращает итератор, указывающий на первый элемент в диапазоне [first, last) , значение которого больше или равно заданному значению «val» . Но в массиве пар lower_bound () для пары (x, y) вернет итератор, указывающий на позицию пары, первое значение которой больше или равно x, а второе значение больше, чем равно y .
    Если вышеупомянутые критерии не соблюдены, то он возвращает итератор к индексу, который находится вне массива пар.
  • upper_bound (): возвращает итератор, указывающий на первый элемент в диапазоне [first, last) , значение которого больше заданного значения «val» . Но в массиве пар upper_bound () для пары (x, y) вернет итератор, указывающий на позицию пары, первое значение которой больше x, а второе значение больше y .
    Если вышеупомянутые критерии не соблюдены, то он возвращает итератор к индексу, который находится вне массива пар.

Синтаксис:

// For lower bound
lower_bound(array_name, array_name + array_size, value, comparator_function);

// For upper bound
upper_bound(array_name, array_name + array_size, value, comparator_function);

Параметры: функции lower_bound () и upper_bound () в массиве пар принимают следующие параметры:

  1. array_name & array_size: имя и размер массива, который представляет интервал между [начало, конец) .
  2. value: значение lower_bound () / upper_bound () для поиска в диапазоне.
  3. Comparator_function: двоичная функция, которая принимает на вход два аргумента, а именно элемент пары типов из массива, а второй - это значение, для которого необходимо найти lower_bound () / upper_bound (), и возвращает логическое значение.

Тип возвращаемого значения: он возвращает итератор, указывающий на первый элемент массива, первый параметр которого больше или равен значению.

Below is the program to demonstrate lower_bound() and upper_bound() in array of pairs:

C++

// C++ program to demonstrate lower_bound()
// and upper_bound() in Array of Pairs
#include <bits/stdc++.h>
using namespace std;
  
// Function to implement lower_bound()
void findLowerBound(pair<int, int> arr[],
                    pair<int, int>& p,
                    int n)
{
    // Given iterator points to the
    // lower_bound() of given pair
    auto low = lower_bound(arr, arr + n, p);
  
    cout << "lower_bound() for {2, 5}"
         << " is at index: "
         << low - arr << endl;
}
  
// Function to implement upper_bound()
void findUpperBound(pair<int, int> arr[],
                    pair<int, int>& p,
                    int n)
{
    // Given iterator points to the
    // lower_bound() of given pair
    auto up = upper_bound(arr, arr + n, p);
  
    cout << "upper_bound() for {2, 5}"
         << " is at index: "
         << up - arr << endl;
}
  
// Driver Code
int main()
{
    // Given sorted array of Pairs
    pair<int, int> arr[]
        = { { 1, 3 }, { 1, 7 }, { 2, 4 },
            { 2, 5 }, { 3, 8 }, { 8, 6 } };
  
    // Given pair {2, 5}
    pair<int, int> p = { 2, 5 };
  
    // Size of array
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Function Call to find lower_bound
    // of pair p in arr
    findLowerBound(arr, p, n);
  
    // Function Call to find upper_bound
    // of pair p in arr
    findUpperBound(arr, p, n);
    return 0;
}
Output:
lower_bound() for {2, 5} is at index: 3
upper_bound() for {2, 5} is at index: 4
Want to learn from the best curated videos and practice problems, check out the C++ Foundation Course for Basic to Advanced C++ and C++ STL Course for the language and STL.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

РЕКОМЕНДУЕМЫЕ СТАТЬИ