Двоичный поиск определяется как алгоритм поиска, используемый в отсортированном массиве путем многократного деления интервала поиска пополам. Идея двоичного поиска состоит в том, чтобы использовать информацию о том, что массив отсортирован, и уменьшить временную сложность.

  • Временная сложность: 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”, который улучшает поиск за счет рекурсивного деления массива.

Надеюсь, эта статья поможет. Большое спасибо за чтение. :)