Учебники

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

Декабрь 12, 2018

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

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

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

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

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

BST Шаг первыйBST Шаг второйBST Шаг третийBST Шаг четвертый

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

Зондирование позиции в интерполяционном поиске

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

Шаг интерполяции первыйШаг второй интерполяции

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

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, нажмите здесь .

91
Share: