Бинарный (двоичный) поиск

Этот листок посвящен бинарному (двоичному) поиску. Бинарный поиск позволяет найти данный элемент в отсортированном массиве или определить, что он не встречается в данном массиве за O(log n) действий, где n - количество элементов в массиве.
Бинарный поиск должен быть реализовать следующей функцией:
int BinSearch (int Arr[], int size, int key)
где Arr - массив, в котором ищется элемент, size - размер массива, key - элемент, который ищется.
Функция возвращает такое значение i, что A[i]==keу, или значение -1, если среди элементов A[0]...A[size-1] нет значения key.
Функция может быть нерекурсивной или рекурсивной. В случае рекурсивной функции необходимо добавить еще один параметр - номер начального элемента диапазона, в котором осуществляется поиск.

Во всех задачах этого листка данные читаются из файла input.txt, результат выводится в файл output.txt.

А. Разминка

Реализуйте алгоритм бинарного поиска в данном отсортированном массиве. Реализация должна быть нерекурсивной. Поиск должен быть бинарным, а не тернарным (т.е. внутри основного цикла не должно отдельно анализироваться совпадение искомого элемента со средним элементом диапазона).

На вход программа получает два числа: N и K, не превосходящие 105. Во второй строке содержится N чисел первого массива, отсортированные по возрастанию. В третьей строке содержится K чисел второго массива. Все числа натуральные, умещающиеся в 32-битный тип int.

Выведите для каждого из K чисел второго массива слово YES, если это число встречается в первом массиве и слово NO в противном случае

Пример

Ввод Вывод 
5 4
1 4 5 8 9
5 6 1 9
 
YES
NO
YES
YES

B. Первое вхождение

Даны два массива, как в предыдущей задаче. Для каждого элемента второго массива выведите индекс его первого появления в первом массиве (число от 0 до N-1, где N – количество элементов в первом массиве), или значение -1, если этот элемент в массиве отсутствует.

Ограничения на решение: бинарный поиск должен быть реализован при помощи рекурсии, и должен быть бинарным (а не тернарным): допускается использование только двух инструкций if в теле функции бинарного поиска (один if  – проверка условия окончания поиска, второй if  – деление отрезка пополам).

Пример

Ввод Вывод 
5 4
1 2 2 3 4
0 1 2 3
 
-1 0 1 3

C. Приближенный двоичный поиск

Заданы два массива, как в первой задаче. Для каждого из K элементов второго массива выведите число из первого массива, наиболее близкое к данному. Если таких чисел несколько - выведите наименьшее из них.

Пример

Ввод Вывод 
5 4
1 4 5 8 10
5 6 1 9
 
5 5 1 8

D. Коровы - в стойла

На прямой расположены стойла, заданы их координаты. Необходимо расставить данное число коров (меньшее количество стойл) так, чтобы минимальное расстояние между коровами было как можно больше.
В первой строке входных данных содержится два числа: количество стойл N и количество коров K, 1≤K<N≤10000. Далее идет N натуральных чисел - координаты стойл в порядке возрастания. Координаты не превосходят 109.
Выведите одно число - наибольшее возможное допустимое расстояние.

Пример

Ввод Вывод 
5 3
1 2 3 100 1000
 
99
Указание. Пусть d - это ответ на эту задачу. Напишите функцию, которая по данному d проверяет, можно ли расставить коров на расстоянии не менее d друг от друга. Далее нам нужно найти такое максимальное d, для которого функция возвращает true. Это можно сделать бинпоиском, т.к. d=1 заведомо подходит, а d=109+1 заведомо не подходит. Такой метод решения задачи называется "Бинарный поиск по ответу".