Структура данных - поиск с интерполяцией

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

Двоичный поиск имеет огромное преимущество во временной сложности перед линейным поиском. Линейный поиск имеет сложность наихудшего случая Ο (n), тогда как двоичный поиск имеет сложность (log n).

Бывают случаи, когда местоположение целевых данных может быть известно заранее. Например, в случае телефонного справочника, если мы хотим найти телефонный номер Морфиуса. Здесь линейный поиск и даже двоичный поиск будут казаться медленными, поскольку мы можем напрямую перейти в область памяти, где хранятся имена, начинающиеся с «M».

Позиционирование в двоичном поиске

При бинарном поиске, если нужные данные не найдены, остальная часть списка делится на две части: нижнюю и верхнюю. Поиск ведется в любом из них.

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

Определение положения в поиске с интерполяцией

Поиск с интерполяцией находит конкретный элемент, вычисляя положение зонда. Первоначально позиция зонда - это позиция самого среднего элемента коллекции.

Если совпадение происходит, возвращается индекс элемента. Чтобы разделить список на две части, мы используем следующий метод -

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

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

Сложность выполнения алгоритма интерполяционного поиска составляет Ο(log (log n)) по сравнению с Ο(log n) BST в благоприятных ситуациях.

Алгоритм

Поскольку это импровизация существующего алгоритма BST, мы упоминаем шаги по поиску «целевого» индекса значения данных с использованием определения положения -

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

Псевдокод

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

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