Перейти на PRO

Приведи пример эффективного алгоритма поиска и объясни его принцип.

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

Ответ

Бинарный поиск (Binary Search) — классический эффективный алгоритм поиска элемента в отсортированном массиве.

Принцип работы ("разделяй и властвуй"):

  1. Сравниваем искомый элемент (key) со средним элементом массива.
  2. Если они равны — поиск завершен.
  3. Если key меньше среднего элемента — повторяем поиск в левой половине массива.
  4. Если key больше — повторяем поиск в правой половине.
  5. Процесс повторяется, пока подмассив для поиска не станет пустым.

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

func binarySearch<T: Comparable>(_ array: [T], key: T) -> Int? {
    var low = 0
    var high = array.count - 1

    while low <= high {
        let mid = (low + high) / 2 // Индекс среднего элемента
        if array[mid] == key {
            return mid // Элемент найден
        } else if array[mid] < key {
            low = mid + 1 // Ищем в правой половине
        } else {
            high = mid - 1 // Ищем в левой половине
        }
    }
    return nil // Элемент не найден
}

// Пример использования
let sortedNumbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
if let index = binarySearch(sortedNumbers, key: 23) {
    print("Элемент найден на индексе: (index)") // Напечатает: 5
}

Ключевые характеристики:

  • Сложность: O(log n), что намного быстрее линейного поиска O(n) для больших массивов.
  • Предварительное условие: Массив должен быть отсортирован.
  • Применение: Используется в реализациях множеств (Set), словарей (Dictionary), при поиске в больших отсортированных наборах данных.

Ответ 18+ 🔞

Давай разберём эту тему, а то некоторые до сих пор линейным поиском по массиву на десять тысяч элементов шарятся, как слепые котята, блядь.

Вот смотри, есть у тебя список, но не абы какой, а отсортированный по полной программе. И тебе надо найти в нём одну конкретную цифру. Можно, конечно, тупо с начала перебирать, как Герасим Муму искал. Но это же, ёпта, долго и унизительно, особенно если список длинный. Надо умнее.

Бинарный поиск — это как раз про ум. Принцип проще пареной репы, хоть и звучит пафосно: «разделяй и властвуй». Суть в чём:

  1. Берёшь весь массив, смотришь на самый серединный элемент.
  2. Если это твой искомый ключ — поздравляю, ты красава, поиск окончен.
  3. Если твой ключ меньше серединного — значит, он где-то в левой половине, и всю правую половину можно выкинуть нахуй, она нас больше не интересует.
  4. Если ключ больше — аналогично, выкидываем левую половину и копаем в правой.
  5. Повторяешь этот цирк с оставшейся половинкой, пока не найдёшь элемент или пока делить уже будет нечего (тогда его там просто нет, пиздец).

Вот как это выглядит в коде на Swift, чтоб не быть голословным:

func binarySearch<T: Comparable>(_ array: [T], key: T) -> Int? {
    var low = 0
    var high = array.count - 1

    while low <= high {
        let mid = (low + high) / 2 // Вот он, центр вселенной на текущем шаге
        if array[mid] == key {
            return mid // Бинго! Нашёл, сука!
        } else if array[mid] < key {
            low = mid + 1 // Ключ больше, значит он правее. Отрезаем левую часть.
        } else {
            high = mid - 1 // Ключ меньше, значит он левее. Отрезаем правую часть.
        }
    }
    return nil // Проехали. Элемента нет. Полный облом.
}

// Пример, чтоб не на пальцах объяснять
let sortedNumbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
if let index = binarySearch(sortedNumbers, key: 23) {
    print("Элемент найден на индексе: (index)") // Напечатает: 5
}

А теперь главное, что делает этот алгоритм охуенным:

  • Скорость — просто космос. Сложность O(log n). Это значит, что чтобы найти элемент в массиве из миллиона чисел, ему нужно сделать не миллион проверок, а всего около 20. Представляешь разницу? Пока линейный поиск будет там ползать, бинарный уже всё нашёл и пошёл пить чай.
  • НО, блядь, важное условие! Массив обязательно должен быть отсортирован. Иначе этот алгоритм превращается в беспомощную мартышку, которая будет искать хуй пойми что и где. Это как искать книгу в библиотеке, где все книги сброшены в одну кучу посреди зала — никакое «деление пополам» не спасёт.
  • Где это применяется? Да везде, где есть порядок и нужно быстро искать: внутри Set, Dictionary, в системных вызовах, в базах данных для индексов. В общем, везде, где программисты не ебланы и думают о производительности.

Вот и вся магия. Просто, элегантно и дохуя эффективно. Главное — не забывай сортировать данные перед использованием, а то будешь потом сидеть и чесать репу, почему не работает, ебать мои старые костыли.

© ХакСобесов, 2026
support@hacksobesov.com