Структура данных и алгоритмы бинарного поиска

Бинарный поиск - это быстрый алгоритм поиска со сложностью во время выполнения Ο (log n). Этот алгоритм поиска работает по принципу «разделяй и властвуй». Чтобы этот алгоритм работал правильно, сбор данных должен быть в отсортированной форме.

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

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

Чтобы бинарный поиск работал, необходимо, чтобы целевой массив был отсортирован. Мы изучим процесс бинарного поиска на наглядном примере. Ниже представлен наш отсортированный массив, и давайте предположим, что нам нужно найти местоположение значения 31 с помощью бинарного поиска.

Бинарный поиск

Во-первых, мы определим половину массива, используя эту формулу -

mid = low + (high - low) / 2

Вот оно, 0 + (9 - 0) / 2 = 4 (целое значение 4,5). Итак, 4 - середина массива.

Бинарный поиск

Теперь мы сравниваем значение, хранящееся в местоположении 4, с искомым значением, то есть 31. Мы находим, что значение в местоположении 4 равно 27, что не совпадает. Поскольку значение больше 27, и у нас есть отсортированный массив, мы также знаем, что целевое значение должно находиться в верхней части массива.

Бинарный поиск

Мы меняем наш минимум на середину + 1 и снова находим новое среднее значение.

low = mid + 1
mid = low + (high - low) / 2

Нашей новой середине сейчас 7. Мы сравниваем значение, хранящееся в местоположении 7, с нашим целевым значением 31.

Бинарный поиск

Значение, хранящееся в местоположении 7, не совпадает, а больше, чем мы ищем. Таким образом, значение должно быть в нижней части от этого места.

Бинарный поиск

Следовательно, мы снова вычисляем середину. На этот раз это 5.

Бинарный поиск

Мы сравниваем значение, хранящееся в местоположении 5, с нашим целевым значением. Мы находим, что это совпадение.

Бинарный поиск

Мы заключаем, что целевое значение 31 хранится в местоположении 5.

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

ПСЕВДОКОД

Псевдокод алгоритмов двоичного поиска должен выглядеть так:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Чтобы узнать о реализации бинарного поиска с использованием массива на языке программирования C, пожалуйста, нажмите здесь .