Обсуждение двоичного поиска и того, как использовать его код шаблона с двумя указателями для решения нескольких вопросов собеседования на C # для лучшего понимания структуры данных и алгоритмов.
Цель
Цель состоит в том, чтобы поделиться некоторыми краткими заметками о двоичном поиске и его реализации с использованием алгоритма рекурсии и двух указателей. Будем надеяться, что сводные заметки высокого уровня позволят вам добавить двоичный поиск в свою сумку с инструментами, не забиваясь подробными объяснениями из учебников. Покрываются следующие элементы:
- Алгоритм логики высокого уровня
- Типичные варианты использования / вопросы на собеседовании со ссылкой на LeetCode
- Типичные ошибки / ошибки в реализации
Что такое двоичный поиск?
Двоичный поиск - это алгоритм поиска в отсортированном массиве целевого значения. Важные примечания о двоичном поиске:
- O (logn) временная сложность, так как размер задачи уменьшается вдвое после каждой итерации.
- O (1) пространственная сложность
- работает с отсортированными массивами
Классические вопросы для собеседования о двоичном поиске:
- Найти положение элемента в отсортированном массиве
- Найти первую позицию элемента в отсортированном массиве
- Найти последнюю позицию элемента в отсортированном массиве
- Пиковый индекс в горном массиве
- так далее..
Что такое два указателя? Эти краткие заметки и код шаблона описаны в моей предыдущей статье: Сводные заметки по алгоритмам - два указателя с кодом шаблона
Двоичный поиск с использованием рекурсии
Обратная сторона
- Рекурсия использует стек, который представляет собой небольшой объем памяти, выделенный процессору, например, 8M, и используется для хранения локальных переменных и стеков вызовов. Когда рекурсия является глубокой рекурсией, например, последовательность Фибоначчи, возможно переполнение стека.
Двоичный поиск с использованием двух указателей (рекомендуется)
Важные примечания к шаблону двоичного поиска:
- Пограничные случаи: ноль, длина равна 0
- while (start + 1 ‹end) // избегаем бесконечного цикла, выходим, когда начало и конец находятся рядом
- середина = начало + (конец - начало) / 2; // начало и конец близки к 2³² будут переполнены
- начало = середина; // не нужно mid + 1, чтобы не потерять цель.
- конец = середина; // не нужно в середине - 1, чтобы не потерять цель.
- Необходимо проверить число [начало] и число [конец]
Ниже приведен шаблон, который можно использовать для решения большинства вариантов двоичного поиска.
С помощью настройки пары строк этот шаблон может решить множество вариантов задач двоичного поиска. Например:
- Найти первую позицию элемента в отсортированном массиве
- Найти последнюю позицию элемента в отсортированном массиве
Вместо того, чтобы возвращать mid в строке 27 выше, нам просто нужно:
- установите end = mid при поиске первой позиции элемента
- установите start = mid при поиске последней позиции элемента
И настройте последовательность проверки nums [начало] и nums [конец].
Отслеживание двоичного поиска
Пиковый индекс в горном массиве:
Еще более простой тестовый пример:
Как видите, решение почти такое же, как и в шаблоне двоичного поиска, с использованием двух указателей выше:
Резюме
Мы представили шаблон двоичного поиска, использующий два указателя, начало и конец, без рекурсии. Шаблон можно легко применить для решения следующих вопросов собеседования:
- Найти положение элемента в отсортированном массиве
- Найти первую позицию элемента в отсортированном массиве
- Найти последнюю позицию элемента в отсортированном массиве
- Пиковый индекс в горном массиве
Пример кода взят из репозитория GitHub, в котором размещен набор алгоритмов, наиболее часто задаваемых в интервью по коду. Репо активно развивается.
