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

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