Практика: Бинарный поиск

Двенадцать задач на отсортированных данных. Первые девять — функция из урока с одной изменённой строкой; напишите её один раз, проверьте на примерах и сохраните. В нескольких условиях разрешено n = 0: тогда вторая строка пустая, цикл выполняется 0 раз, а ответ — «не найдено».

• «Find in Sorted Array»: функция из урока как есть.
• «First Occurrence», «Last Occurrence», «Count Equal Values»: когда a[m] == x, не останавливайтесь — запомните m и ищите дальше левее (первое) или правее (последнее). Количество — это последнее − первое + 1 или 0.
• «Insertion Position»: первый индекс с a[i] >= x; когда a[m] < x, двигайте l, иначе запомните m и двигайте r. Ответ может быть n + 1.
• «Floor Value» и «Ceiling Value»: наибольшее a[i] <= x, наименьшее a[i] >= x или NONE — тот же поиск, только запоминается значение, а не индекс.
• «Closest Sorted Queries»: единственные два кандидата — первый элемент >= x и элемент прямо перед ним; при ничьей — меньшее значение, затем меньший индекс. Значения достигают 10¹⁸.
• «Count in a Value Range»: (первый индекс > r) − (первый индекс >= l), два поиска на запрос.
• «First One»: отсортированный ряд из 0 и 1 — первая единица — это первый элемент >= 1.
• «Worms»: постройте накопленные суммы t[i] = червей в кучах 1..i; они возрастают, поэтому куча с номером q — это первое i, для которого t[i] >= q.
• «Flattened Matrix Search»: строки, записанные подряд, образуют один отсортированный вектор из n·m значений; найдите число в нём, а затем превратите индекс k обратно в строку k / m и столбец k % m.