Что такое upper_bound и lower_bound в c++ и чем они отличаются

Ну, например, у вас есть упорядоченная (важно!) последовательность

1 2 3 4 4 4 5 5 5 5 5 6 7

При поиске upper_bound для значения 5 это будет итератор (указатель, если концепция итератора для вас нова) на значение 6 - первое большее значение.

Соответственно, lower_bound будет указывать на первое не меньшее значение - на первое 5.

Например, код

int main(int argc, const char * argv[])
{
    int a[20] = { 1,2,3,4,5,6,7,7,7,8,9,9,11,11,12,16,20,20,20,20 };
    for(int * p = lower_bound(a,a+20,10);
        p != upper_bound(a,a+20,20); ++p)
        cout << *p << " ";
    cout << endl;
}

дает

11 11 12 16 20 20 20 20