в программировании на Swift …….

ЧАСТЬ - 4

Поиск с интерполяцией, также известный как поиск с экстраполяцией, - это метод поиска определенного значения в упорядоченном массиве. Поиск с интерполяцией является улучшением по сравнению с двоичным поиском, например, когда значения в отсортированном массиве равномерно распределены (означает, что промежутки между элементами массива должны быть одинаковыми). Двоичный поиск всегда переходит к среднему элементу для проверки. С другой стороны, поиск с интерполяцией может идти в разные места в соответствии со значением ищущего ключа. Если значение ключа ближе к последнему элементу, поиск с интерполяцией, вероятно, начнет поиск по направлению к конечной стороне, чтобы найти позицию для поиска.

Работа алгоритма поиска с интерполяцией

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

Предположим, что имеется массив itemArray из n элементов, в котором элементы расположены в отсортированном порядке. Первоначально низкий уровень установлен на 0, а высокий - на n-1. Теперь мы ищем значение VAL в itemArray между itemArray [LOW] и itemArray [HIGH]. Тогда в этом случае MID будет рассчитываться по следующей формуле: MID = LOW + (HIGH - LOW) X ((VAL - itemArray [LOW] / itemArray [HIGH] - itemArray [LOW])) если значение VAL найдено в MID, то поиск завершен; в противном случае, если значение ниже, чем itemArray [MID], сбросить HIGH = MID-1, а если значение больше, чем itemArray [MID], сбросить LOW = MID +1. Повторяйте эти шаги, пока значение не будет найдено.

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

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

Пошаговый поиск с интерполяцией

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

Сложность интерполяционного поиска: -

Поиск с интерполяцией производит сравнение примерно log10 (log10 n), когда в списке имеется n элементов, и элементы распределены равномерно. в худшем случае алгоритм может выполнить до O (n) сравнений.

Преимущества и недостатки интерполяционного поиска

Преимущество: - Когда все элементы в списке отсортированы и равномерно распределены, время выполнения алгоритма поиска с интерполяцией составляет log (log n). То есть в лучшем случае.

Недостаток: - Когда элементы в списке увеличиваются экспоненциально, время выполнения алгоритма поиска с интерполяцией составляет O (n). т.е. худший случай

Поиск с интерполяцией в Swift

Спасибо за прочтение……..

В Части -5 Остальные поиски ……………

  • ***************************!!!Увидимся!!!*************** ********

Таким образом, цель алгоритмов - решить проблему повторяющимся образом. Впереди еще много всего. Я планирую написать серию сообщений в блоге об алгоритмах и более подробно расскажу о структурах данных с использованием языка программирования Swift.

Моя предыдущая статья: -

Линейный поиск Бинарный поиск и Поиск с переходом и Черно-белый линейный и двоичный поиск