Двоичный поиск определяется как алгоритм поиска, используемый в отсортированном массиве путем многократного деления интервала поиска пополам. Идея двоичного поиска состоит в том, чтобы использовать информацию о том, что массив отсортирован, и уменьшить временную сложность.
- Временная сложность: O(log N)
- Лучший случай:O(1) , когда целевой элемент находится в середине отсортированного массива.
Он должен иметь три входа
- Сортированный массив
- Целевое значение для поиска
- индексы диапазона поиска
Алгоритм двоичного поиска можно реализовать двумя способами.
- Итеративный
- Рекурсивный
Шаги итеративного двоичного поиска
- Получить отсортированный массив
- Сравните целевое значение со значением в среднем индексе массива.
- Три случая
- Если целевое значение равно среднему элементу, поиск успешен и возвращает индекс среднего элемента.
- Если целевое значение меньше среднего элемента, обновите конечный индекс диапазона поиска до среднего индекса минус один и повторите процесс, начиная с шага 2.
- Если целевое значение больше среднего элемента, обновите начальный индекс диапазона поиска, указав средний индекс плюс один, и повторите процесс, начиная с шага 2.
Код
Шаги рекурсивного двоичного поиска
- Получить отсортированный массив
- Сравните, граница
left
превышает границуright
, это указывает на то, что целевой элемент отсутствует в текущем пространстве поиска. - Вычислите средний индекс
mid
в текущем пространстве поиска. Это гарантирует, что средний индекс будет вычислен без возникновения проблем целочисленного переполнения, даже для больших значенийleft
иright
. - Убедитесь, что элемент со средним индексом
mid
соответствует целевому значению, функция возвращаетmid
, указывая, что целевой элемент найден. - Если элемент
mid
меньше целевого значения, это предполагает, что целевой элемент должен находиться в правой половине текущего пространства поиска. Вызовите функцию рекурсивно с обновленной границейleft
(mid+1
), сохраняя при этом границуright
неизменной. - Если элемент
mid
больше целевого значения, это означает, что целевой элемент находится в левой половине текущего пространства поиска. Вызовите функцию рекурсивно с обновленной границейright
(mid-1
), сохраняя при этом границуleft
неизменной. - Функция использует подход
divide-and-conquer
для рекурсивного поиска целевого элемента во все меньших и меньших подмассивах до тех пор, пока цель не будет найдена или пространство поиска не будет исчерпано.
Код
Пакет ломтиков
В последней версии golang 1.21
представлен новый пакет slices
, который обеспечивает несколько общих операций над срезами.
Поскольку этот пакет имеет функцию BinarySearch
Заключение
Бинарный поиск — это широко используемый алгоритм в информатике, который используется для поиска элемента в отсортированном списке элементов. Это эффективный алгоритм, который делит отсортированные данные на две половины и анализирует данные в точке разделения. Двоичный поиск — более специализированный алгоритм, чем последовательный поиск, поскольку он использует отсортированные данные. Это алгоритм “divide and conquer”
, который улучшает поиск за счет рекурсивного деления массива.
Надеюсь, эта статья поможет. Большое спасибо за чтение. :)