Двоичный поиск: алгоритм, примеры на C и Python, нюансы использования

Начинаем цикл статей, где можно будет простыми словами изучить алгоритмы.​

Данный цикл полезен будет для подготовки к собесам и если вы хотите изучить базовые алгоритмы и структуры данных.​

​

Будем рассматривать питон и Си.​

А также сравнительный анализ этих языков для решения алгоритмических задач.​

​

🔍 Двоичный поиск: алгоритм, примеры на C и Python, нюансы использования​


1747319047943.png


  • Что делать, если у вас отсортированный массив, и нужно быстро найти элемент?
  • Правильный ответ: применить двоичный (бинарный) поиск.
  • Он работает в логарифмическом времени: O(log₂ n).
  • Это один из базовых, но при этом часто используемых алгоритмов в программировании.

📘 Что такое двоичный поиск?​


Представьте, что вы ищете слово в словаре. Вы не листаете по одной странице — вы раскрываете словарь в середине, смотрите, в каком направлении двигаться — и снова делите пополам.

Вот так же работает и двоичный поиск.

➡️ Условие: данные должны быть уже отсортированы по возрастанию или убыванию.
➡️ Принцип: делим массив пополам, сравниваем с серединой, исключаем половину, повторяем.


🔢 Пример на языке C​


C: 
#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    int left = 0, right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;  // нашли!
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;  // не найден
}

int main() {
    int numbers[] = {3, 8, 15, 23, 42, 55, 60};
    int index = binary_search(numbers, 7, 23);

    if (index >= 0)
        printf("Найдено на позиции %d\n", index);
    else
        printf("Элемент не найден\n");

    return 0;
}

Почему ?
Код: 
 int mid = left + (right - left) / 2

Это защита от переполнения при сложении:
если left + right превысит INT_MAX, произойдёт integer overflow.

Вместо этого безопасно сначала вычислить (right - left) / 2 — это гарантированно меньше диапазона int, и только потом прибавить left.

А вот в питоне можно:

Код: 
mid = (left + right) // 2

Здесь можно безопасно сложить left + right, потому что Python использует произвольную точность для целых чисел (big integers).

Также про это будет рассказано в следующих статьях.)

🐍 Пример на Python

Python: 
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid  # найден
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # не найден

nums = [3, 8, 15, 23, 42, 55, 60]
index = binary_search(nums, 23)

if index >= 0:
    print(f"Найдено на позиции {index}")
else:
    print("Элемент не найден")


💡 C vs Python: нюансы реализации​

  1. 🔧 C даёт полный контроль над памятью — придётся вручную считать границы, выделять массив, компилировать.
  2. 🐍 Python проще и нагляднее, особенно для обучения, но его скорость ниже.
  3. ⚙️ На больших объёмах данных C покажет себя лучше по производительности.
  4. 📚 Python же хорош как "скетчборд" — для прототипирования и отладки.


📉 Временная сложность​


ОперацияСложность
Лучший случайO(1) – элемент в центре
Средний случайO(log n)
Худший случайO(log n)


🧠 Почему важно понимать двоичный поиск?​

  • Он — основа многих алгоритмов, включая поиск в словарях, базах данных, деревьях.
  • Работает везде, где есть отсортированные структуры.
  • Часто используется на собеседованиях (Google, Яндекс, VK).
  • Иногда возникает необходимость его модифицировать — например, найти первое вхождение.


🧪 Вариации и практики​


✅ Бинарный поиск по ответу (Binary Search on the Answer)
✅ Бинарный поиск в непрямом массиве (через функцию)
✅ Поиск границы (нижней/верхней)
✅ Рекурсивная реализация — тоже возможна, но менее популярна из-за нагрузки на стек.


📎 Вывод​


Если вы ещё не реализовали двоичный поиск "вручную" — сделайте это. На C, на Python, хоть на бумаге. Понимание этого простого, но мощного алгоритма — ключевой шаг к более сложным концепциям: деревьям, графам, индексированным поискам.


💬 А вы где применяли бинарный поиск на практике? Делитесь в комментариях — особенно, если приходилось его модифицировать!