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

Бинарный поиск — это быстрый алгоритм поиска со сложностью во время выполнения Ο (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, пожалуйста, нажмите здесь .