Бинарный поиск (binary_search, lower_bound, upper_bound)

binary_search
Формулировка задачи: Узнать, находится ли данный элемент в отсортированном массиве подобных элементов, для которых задано отношение порядка на множестве. Т.е. имея в наличии два элемента, можно однозначно определить операцию <. Сложность O(log(N)).
Реализация:

1. bool binary_search(const vector<int> &mas, const int &value)
2. {
3.   int l = 0, r = mas.size()-1;
4.   while (l<r)
5.   {
6.     int m = (l+r)>>1;
7.     if (mas[m] < value)
8.       l = m +1;
9.     else if (mas[m] > value)
10.       r = m - 1;
11.     else
12.       return true;
13.   }
14.   return mas[l] == value;
15. }

* This source code was highlighted with Source Code Highlighter.

Длинное + длинное

[Вся длинная арифметика]

Операция сложения двух длинных чисел:

1. BigInt operator + (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   res.amount = max(a.amount,b.amount);
5.   int r = 0;
6.   for (int i=0;i<res.amount | r;i++)
7.   {
8.     res.digits[i] = a.digits[i] + b.digits[i] + r;
9.     if (res.digits[i]>=osn)
10.     {
11.       res.digits[i]-=osn;
12.       r = 1;
13.     }
14.     else
15.       r = 0;
16.   }
17.   if (res.digits[res.amount])
18.     res.amount++; 
19.  
20.   return res;
21. }

* This source code was highlighted with Source Code Highlighter.

В данной реализации отсутствует операция взятия остатка от деления. Вместо этого используется вычитание значения основания системы счисления в строке 11.

P.S: Данная реализация появилась на основе статьи Виталия Гольдштейна с учетом оформления длинных чисел команды HotFinnKeys.