в программировании на 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.
Моя предыдущая статья: -
Линейный поиск Бинарный поиск и Поиск с переходом и Черно-белый линейный и двоичный поиск