Семинар 22.01 Подгруппа 106-2

Домашнее задание:

1. Написать функцию lower_bound и тесты к ней.

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

Код необходимо отправить на ревью.

2. Решить рекурентное соотношение F(n) = F(n/2) + F(n/3) + cn

(*) 3. Придумать любой алгоритм, который находит число в отсортированной последовательности, если оракул врет, но не более одного раза. Подумать над алгоритмом, который использует менее 2logn+1 сравнений.