2.1.11 Двоичный поиск

Дан массив из n целых чисел, отсортированный по неубыванию, и целое число x. Найдите индекс первого вхождения числа x в массив. Если число отсутствует, результатом поиска должно быть −1. Индексация начинается с нуля.

Реализуйте поиск в отдельной функции int binary_search_first(const int array[], int n, int x). Используйте алгоритм двоичного поиска: сравнивайте искомое число с элементом в середине рассматриваемого диапазона и сокращайте диапазон поиска. Если найден элемент, равный x, продолжайте поиск первого вхождения среди элементов левее него. Функция не должна изменять массив или выполнять ввод и вывод.

В функции main прочитайте входные данные, вызовите binary_search_first и выведите её результат. Линейный перебор массива и использование готовых функций поиска, включая bsearch, std::binary_search и std::lower_bound, запрещены. Количество проверяемых элементов должно расти не быстрее O(log n); повторяющиеся значения не должны приводить к линейному поиску первого вхождения.

Материал к заданию

Бинарный поиск — Хабр. Примеры написаны на JavaScript. Перенесите принцип сокращения диапазона поиска на C или C++, соблюдая интерфейс из условия. Для этой задачи требуется первое вхождение: после обнаружения равного элемента продолжайте поиск слева; линейный проход по повторяющимся элементам не допускается.

Время: 2 секунды. Память: 64 МиБ. Вывод: до 2 МиБ. Стандарты: C11 / C++17.

В первой строке вводится целое число n — количество элементов массива. Во второй строке вводятся n целых чисел, разделённых пробелами, в порядке неубывания. В третьей строке вводится целое число x. Ограничения: 1 ≤ n ≤ 10000, −10⁹ ≤ aᵢ, x ≤ 10⁹. Значения элементов могут повторяться.

Одно целое число — индекс первого вхождения x в массив либо −1, если такого элемента нет.