Приведи пример реализации алгоритма бинарного поиска в отсортированном массиве.

Question

Приведи пример реализации алгоритма бинарного поиска в отсортированном массиве.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C# Разработчик

Ответ

Бинарный поиск — это алгоритм поиска элемента в отсортированном массиве за время O(log n). Принцип работы: на каждом шаге интервал поиска делится пополам, пока элемент не будет найден или интервал не станет пустым.

Реализация на C# (итеративный подход):

public static int BinarySearch(int[] sortedArray, int target)
{
    // Границы текущего интервала поиска
    int left = 0;
    int right = sortedArray.Length - 1;

    while (left <= right)
    {
        // Вычисление середины с защитой от переполнения
        int mid = left + (right - left) / 2;

        if (sortedArray[mid] == target)
        {
            return mid; // Элемент найден
        }
        else if (sortedArray[mid] < target)
        {
            // Искомый элемент в правой половине
            left = mid + 1;
        }
        else
        {
            // Искомый элемент в левой половине
            right = mid - 1;
        }
    }
    // Элемент не найден
    return -1;
}

Объяснение ключевых моментов:

Условие left <= right: Позволяет обрабатывать интервалы, включая случаи с одним элементом.
Расчёт mid: Используется формула left + (right - left) / 2 вместо (left + right) / 2 для избежания потенциального переполнения при очень больших значениях left и right.
Сдвиг границ: В зависимости от сравнения, мы отбрасываем заведомо неподходящую половину массива.

Пример использования:

int[] data = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
int index = BinarySearch(data, 23); // index = 5
int notFound = BinarySearch(data, 50); // notFound = -1

Для работы с любыми типами можно использовать обобщённую версию с IComparable<T>:

public static int BinarySearch<T>(T[] sortedArray, T target) where T : IComparable<T>
{
    int left = 0, right = sortedArray.Length - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        int comparison = sortedArray[mid].CompareTo(target);
        if (comparison == 0) return mid;
        if (comparison < 0) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Ответ 18+ 🔞

Смотри, объясню тебе про бинарный поиск, как есть. Это же элементарно, Ватсон! Представь, что у тебя есть телефонная книга, толстая такая, дохуя страниц. И ты ищешь какого-нибудь "Иванова". Ты же не будешь листать с первой страницы, ты ж не идиот? Ты её пополам — хрясь! Смотришь: о, середина — это "Петров". "Иванов" раньше. Значит, правую половину книги — нахуй, в мусорку, её вообще можно не смотреть. И так раз за разом эту оставшуюся стопку пополам, пока не найдёшь. Вот и весь алгоритм, гениальный в своей простоте.

А теперь смотри, как это в коде выглядит, на C#. Берём отсортированный массив — это важно, ёпта, иначе нихуя не работает!

public static int BinarySearch(int[] sortedArray, int target)
{
    // Границы — с самого начала и до самого конца
    int left = 0;
    int right = sortedArray.Length - 1;

    // Пока наш отрезок не схлопнулся в ничто
    while (left <= right)
    {
        // Серединку ищем. Вот тут хитрость: нельзя писать (left + right) / 2.
        // А вдруг left и right такие большие, что при сложении улетят за пределы int?
        // Поэтому left + (right - left) / 2 — и никаких переполнений, красота!
        int mid = left + (right - left) / 2;

        if (sortedArray[mid] == target)
        {
            return mid; // Ура, нашли! Возвращаем индекс, довольные как слоны.
        }
        else if (sortedArray[mid] < target)
        {
            // Наш искомый элемент где-то справа, в будущем.
            // Значит, левую границу двигаем сразу за середину.
            left = mid + 1;
        }
        else
        {
            // Искомый элемент слева, в прошлом.
            // Правую границу двигаем перед серединой.
            right = mid - 1;
        }
    }
    // Если сюда вышли — нихуя не нашли. Возвращаем -1, классика жанра.
    return -1;
}

Ну и примерчик, чтобы совсем всё стало ясно, как божий день:

int[] data = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
int index = BinarySearch(data, 23); // index = 5, всё чётко
int notFound = BinarySearch(data, 50); // notFound = -1, такого числа нет, печалька

А если хочешь универсальности, чтобы искать не только int, но и что угодно сравнимое, то вот тебе обобщённая версия. Выглядит страшновато, но работает — пиздец как хорошо.

public static int BinarySearch<T>(T[] sortedArray, T target) where T : IComparable<T>
{
    int left = 0, right = sortedArray.Length - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        int comparison = sortedArray[mid].CompareTo(target);
        if (comparison == 0) return mid; // Нашли!
        if (comparison < 0) left = mid + 1; // Цель справа
        else right = mid - 1; // Цель слева
    }
    return -1; // Не нашли, бывает
}

Вот и вся магия. Быстро, эффективно, O(log n) — мечта, а не алгоритм. Главное — массив должен быть отсортирован, а то получишь полную хуйню.