Лабораторная работа 3. Бинарный поиск

Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном массиве. Он работает по принципу разделяй и властвуй:

1. Находим средний элемент массива.
2. Если искомый элемент равен среднему — нашли
3. Если меньше, продолжаем поиск в левой половине.
4. Если больше, продолжаем в правой половине.
5. Повторяем процесс, пока не найдем элемент или массив не станет пустым.

Сложность алгоритма

• В худшем случае: $O(\log N)$
  
• В лучшем случае: $O(1)$ (если элемент найден сразу)
• В среднем случае: $O(\log N)$

1. Напишите функцию, которая принимает отсортированный массив и число x, а затем возвращает его индекс (или -1, если числа нет в массиве)

2. Массив может содержать повторяющиеся числа. Напишите бинарный поиск, который находит индекс первого появления числа.

3. Допустим, есть массив [1, 2, 2, 2, 3, 4].
Нужно найти левую и правую границу числа 2, то есть 1 и 3.

4. Напишите функцию sqrt(n), которая находит целочисленный квадратный корень числа n с помощью бинарного поиска.

5. Используйте бинарный поиск для нахождения слова в отсортированном списке строк (например, в словаре).