Учебники

8) Алгоритм двоичного поиска

Сентябрь 28, 2019

Прежде чем мы изучим бинарный поиск, давайте изучим:

Что такое поиск?

Поиск — это утилита, которая позволяет пользователю находить документы, файлы, мультимедиа или любые другие типы данных, хранящиеся в базе данных. Поиск работает по простому принципу сопоставления критериев с записями и их отображения пользователю. Таким образом, работает основная функция поиска.

Что такое бинарный поиск?

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

Из этого урока по алгоритму вы узнаете:

Как работает бинарный поиск?

Бинарный поиск работает следующим образом:

  • Процесс поиска начинается с определения местоположения среднего элемента отсортированного массива данных.
  • После этого значение ключа сравнивается с элементом
  • Если значение ключа меньше, чем средний элемент, то поиск анализирует верхние значения для среднего элемента для сравнения и сопоставления
  • В случае, если значение ключа больше, чем средний элемент, поиск выполняет анализ нижних значений для среднего элемента для сравнения и сопоставления.

Пример бинарного поиска

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

Изображение выше иллюстрирует следующее:

  1. У вас есть массив из 10 цифр, и нужно найти элемент 59.
  2. Все элементы помечены индексом от 0 до 9. Теперь вычисляется середина массива. Для этого вы берете левые и правые значения индекса и делите их на 2. В результате получается 4,5, но мы берем минимальное значение. Следовательно, середина 4.
  3. Алгоритм сбрасывает все элементы со средней (4) до нижней границы, потому что 59 больше 24, и теперь в массиве осталось только 5 элементов.
  4. Теперь 59 больше 45 и меньше 63. Середина равна 7. Следовательно, правое значение индекса становится средним — 1, что равно 6, а левое значение индекса остается таким же, как и раньше, то есть 5.
  5. В этот момент вы знаете, что 59 следует за 45. Следовательно, левый индекс, который равен 5, также становится средним.
  6. Эти итерации продолжаются до тех пор, пока массив не будет уменьшен до одного элемента, или элемент, который будет найден, станет серединой массива.

Пример 2

Давайте посмотрим на следующий пример, чтобы понять, как работает бинарный поиск

  1. У вас есть массив отсортированных значений в диапазоне от 2 до 20, и вам нужно найти 18.
  2. Среднее значение нижнего и верхнего пределов составляет (l + r) / 2 = 4. Искомое значение больше среднего, равного 4.
  3. Значения массива, меньшие среднего, удаляются из поиска, а значения, превышающие среднее значение 4, ищутся.
  4. Это повторяющийся процесс деления до тех пор, пока не будет найден фактический искомый предмет.

Зачем нам нужен бинарный поиск?

Следующие причины делают бинарный поиск лучшим выбором для использования в качестве алгоритма поиска:

  • Бинарный поиск эффективно работает с отсортированными данными независимо от размера данных
  • Вместо того, чтобы выполнять поиск, просматривая данные в последовательности, бинарный алгоритм случайным образом обращается к данным, чтобы найти требуемый элемент. Это делает поисковые циклы короче и точнее.
  • Бинарный поиск выполняет сравнение отсортированных данных на основе принципа упорядочения, чем сравнение на равенство, которое медленнее и в большинстве случаев неточно.
  • После каждого цикла поиска алгоритм делит размер массива пополам, поэтому на следующей итерации он будет работать только в оставшейся половине массива.

Резюме

  • Поиск — это утилита, которая позволяет пользователю искать документы, файлы и другие типы данных. Бинарный поиск — это расширенный алгоритм поиска, который находит и выбирает данные из отсортированного списка элементов.
  • Бинарный поиск обычно известен как полуинтервальный поиск или логарифмический поиск
  • Это работает путем деления массива на половину на каждой итерации под требуемым элементом найден.
  • Бинарный алгоритм берет середину массива путем деления суммы левого и правого значений индекса на 2. Теперь алгоритм сбрасывает нижнюю или верхнюю границу элементов из середины массива, в зависимости от найденного элемента. ,
  • Алгоритм случайным образом обращается к данным, чтобы найти нужный элемент. Это делает поисковые циклы короче и точнее.
  • Бинарный поиск выполняет сравнение отсортированных данных на основе принципа упорядочения, а не медленного и неточного сравнения на равенство.
  • Бинарный поиск не подходит для несортированных данных.

 

45
Share: