Задание 1. Двоичный поиск
Во входном файле задан отсортированный массив чисел от 0 до 2 миллиардов. Сначала написано число N, размер массива. Потом выписаны N чисел.
Далее написано число K, за которым следует K чисел x_i, которые надо найти в массиве. Необходимо для каждого числа x_i вывести его индекс в массиве, это номер числа с начала массива, считая с 0. Например, в массиве [10, 20, 30] число 30 имеет индекс 2. Если число не найдено, нужно вывести -1. Если одинаковых чисел несколько, можно вывести любой индекс. Все ответы выводятся в отдельной строке.
Для решения задачи используйте следующий алгоритм. Заведите переменные left и right, которые хранят индексы диапазона поиска числа в массиве. Сначала left=0, right=LENGTH(A)-1. Т.е. мы ищем число от начала до конца массива. На каждом шаге проверяется значение в массиве по индексу ровно посередине между left и right: middle = (left + right)/2 Если оно больше искомого числа, значит, искомое число в левой половине, и нужно переназначить right = middle. Иначе, если оно больше искомого числа, оно в правой половине, и требуется переназначить: left = middle. Последний случай, число совпало с искомым, значит, индекс найден.
Процесс продолжается, пока left и right не сойдутся так, что между ними больше нет других индексов.
В этой программе очень важно правильно разобрать все граничные условия и случаи, иначе очень легко получить бесконечный цикл или неверно работающую программу. Постоянно помните о смысле переменных left и right, проверяйте, не меняется ли их смысл при присваивании. Попробуйте посмотреть, как изменится код, если заменить смысл right на правую границу диапазона поиска, но в которой точно нет значения. Сначала right=LENGTH(A), потом оно должно изменять так, что искомое значение находится от left (включительно) до right (не включительно).
Тесты: https://students.iposov.spb.ru/21spring/algs/binary-search/tests-bin-search.zip
Двоичный поиск по ответу
На прямой дано $N$ точек и число $k$. Вы должны покрыть точки с помощью $k$ одинаковых по длине отрезков, причем требуется определить, какая минимальная длина отрезков подходит в задаче.
Например, если на прямой даны точки $A=10$, $B=15$, $C=30$, $D=40$ и $k=2$, то эти точки можно покрыть отрезками длины 10. Первый отрезок покрывает точки $A$ и $B$, второй — $C$ и $D$.
Если $k=3$, то эти же точки можно покрыть отрезками длины 5. Первый отрезок покрывает точки $A$ и $B$, второй — $C$, третий $D$.
При $k=4$ ответ будет 0. Каждый из четырех отрезков покрывает одну из точек.
Для решения задачи используйте двоичный поиск по ответу. Отрезок длины 0 это самое маленькое возможное значение, а отрезок длины от первой точки до последней — самое большое, такой один отрезок гарантированно покроет все точки.
В стандартном вводе в первой строке дано число $N$, во второй — $k$, далее даны $N$ чисел $0 \le A_i \le 2,000,000,000$. Точки $A_i$ расположены по возрастанию, сортировать массив не требуется.
Выведите в стандартный вывод одно число - минимальную длину отрезков.