Импортозамещение в коде: пишем алгоритм бинарного поиска с нуля за 30 минут

В эпоху технологического суверенитета и импортозамещения речь идет не только о железе и операционных системах. Фундаментом любой IT-инфраструктуры являются алгоритмы — те самые кирпичики логики, из которых строятся программы. Сегодня мы не будем обсуждать замену зарубежного ПО, а займемся импортозамещением в чистом виде: напишем один из ключевых алгоритмов компьютерных наук, бинарный поиск, самостоятельно, с полного нуля. И сделаем это всего за 30 минут. Цель — не просто скопировать код из интернета, а понять его суть, чтобы в будущем вы могли реализовывать подобные решения независимо от внешних источников.

Что такое бинарный поиск? Это эффективный алгоритм поиска элемента в отсортированном массиве. Его принцип напоминает поиск слова в словаре: вы открываете книгу примерно посередине, смотрите, нужно ли вам слово до или после этой страницы, и отбрасываете ненужную половину. Этот процесс повторяется, пока слово не будет найдено. Ключевое преимущество — сложность O(log n), что означает, что даже для массива из миллиона элементов потребуется не более 20 сравнений. В условиях работы с большими данными это не просто оптимизация, а необходимость.

Приступим к созданию. Первый шаг — понимание условий. Наш массив должен быть отсортирован по возрастанию. Это аксиома. На вход функция получит массив и искомое значение. На выходе — индекс этого значения в массиве или -1, если элемента нет.

Начнем писать код на псевдокоде, а затем переведем его в Python, как в один из самых читаемых языков. Определяем функцию binary_search(arr, target). Инициализируем два указателя: left (начало диапазона, изначально 0) и right (конец диапазона, изначально len(arr) — 1). Эти указатели будут обозначать текущий «активный» отрезок массива, где мы ищем элемент.

Основная логика заключена в цикле while left  7, сдвигаем right=3. Третья итерация: left=3, right=3, mid=3, arr[3]=7. Нашли! Возвращаем 3.

Это базовая реализация. Но импортозамещение подразумевает и глубокое понимание. Обсудим краевые случаи. Что если массив пуст? Наша реализация с len(arr)-1 корректно обработает это, так как right станет -1, и цикл while left