std::lower_bound - Büyük Eşittir (>=) Araması

Giriş

Şu satırı dahil ederiz.

#include <algorithm>

İmzası şöyle. Value veya value + comparator ile çalışabilir.

template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,const T& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,const T& value, Compare comp);

Açıklaması şöyle. Yani comparator false dönmediği müddetçe aramaya devam eder.

The furthermost iterator i in the range [first, last] such that for every iterator j in the range [first, i) the following corresponding conditions hold: comp(*j, value) != false.

std::map için Kullanmayın
std::map sınıfının kendi lower_bound() metodu vardır

Dizinin Sıralı Olması
Dizinin sıralı olması gerekir diye biliyordum ancak daha sonra sıralı olmak zorunlululuğu olmadığını öğrendim. Dolayısıyla lower_bound sıralı bir diziye yeni eleman eklemek için kullanılabilir.

Returns an iterator pointing to the first element that is not less than key.

Algoritma belirtilen değer ile iterator'ün değerini şöyle karşılaştırır.

if (*it < value) { ... }

Value ile kullanımı - ilk >= koşulu

Küçükten büyüğe sıralı dizilerde kullanılır. Verilen değerden ">=" olan ilk değeri döndürür. Küçükten büyüğe boy sıralamasında benden bır tık daha uzun veya benimle aynı uzunluktaki ilk kişinin konumunu verir.

Value ile kullanımı - ilk <= koşulu
Büyükten küçüğe sıralı dizilerde kullanılır. Verilen değerden "<=" olan ilk değeri döndürür. Büyükten küçüğe boy sıralamasında benden bır tık daha kısa veya benimle aynı uzunluktaki ilk kişinin konumunu verir.

Örnek

Dolayısıyla arama için kullanılan değerin < operatörünün tanımlı olması gerekir. Elimizde MyInt isimli bir sınıf olsun. Aşağıdaki kodda lower_bound MyInt() için < 2 operatörünü arayacak ve bulacak. Dolayısıyla kod derlenir

#include <set>
#include <algorithm>

using namespace std;

class MyInt {
  public:
    MyInt(int _val): {...}
    bool operator<(const MyInt& other) const {...}
};

set<MyInt> s;
s.insert(1);
s.insert(MyInt(2));
s.insert(3);
set<MyInt>::iterator it = lower_bound(s.begin(), s.end(), 2);

Örnek
Bu bir HackerRank sorusu. Büüykten küçüğe puanlar olsun. Alice'in en üstten kaçıncı olduğunu bulmak için şöyle yaparız. sort() ve lower_bound() çağrılarından büyükten küçüğe sıralama kullanılıyor.

std::vector<int> scores { 100, 100, 50, 40, 40, 20, 10 };
std::vector<int> aliceScores { 5, 25, 50, 120 };
// sort and erase duplicates
std::sort(std::begin(scores), std::end(scores), std::greater<int>());
scores.erase(std::unique(std::begin(scores), std::end(scores)), std::end(scores));

// just a lambda to make the output part more readable
auto locateRanking = [](const auto& _scores, int _newScore){
  auto itr = std::lower_bound(std::begin(_scores), std::end(_scores), _newScore,
    std::greater<int>());
  return std::distance(std::begin(_scores), itr) + 1;
};

// output part
for (auto newScore : aliceScores)
{
  std::cout << locateRanking(scores, newScore) << std::endl;
}

Value + Compartor ile Kullanımı
Örnek
Elimizde şöyle bir kod olsun

const std::vector<int> v{1, 3, 4, 2, 7, 5, 8, 6};

Şöyle yaparız.

auto pred2 = [](int lhs, int rhs){ return (lhs < 5) > (rhs < 5); }
assert(std::is_sorted(v.begin, v.end(), pred2));
auto it2 = std::lower_bound(v.begin, v.end(), 5, pred2);

assert(it1 == it2); // *it1 == 7

Bazı notlar

1. Eğer aranılan değer yoksa, alt sınır için değerden büyük olan ilk elemandan bir önceki konumu döndürür. Bu konum mesela begin () olabilir.

2. Eğer aranılan değer varsa veya bir kaç tane varsa, alt sınır için değerden bir önceki konumu döndürür. 

3. Eğer aranılan değer yoksa, ve tüm değerler aranılandan küçükse, end() döner.

Bu method Java'daki NavigableSet.ceiling() metoduna benziyor. Ancak Java'da verilen iterator aralığının sıralı olması gerekmez.

binary_find metodu
lower_bound binary_find isimli yeni bir metod yazmak için kullanılabilir. Aranan değer varsa iterator değeri döner, yoksa end değerini döner. Böylece STL ile gelen ve sadece boolean dönen binary_search algoritmasının sınırlamasından kurtuluruz.

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}