69
правок
Изменения
Нет описания правки
=== Псевдокод ===
<code style = "display: inline-block;">
'''function ''' interpolation_search(a : '''int[]''', key : '''int''') <font color=green> //a должен быть отсортирован</font> left = 0 <font color=green> // левая граница поиска (будем считать, что элементы массива нумеруются с нуля)</font> right = a.length - 1 <font color=green> // правая граница поиска</font>
'''while ''' a[left] <tex> \le </tex> key '''and ''' key <tex> \le </tex> a[right] mid = left + (key - a[left]) / (a[right] - a[left]) * (right - left) <font color=green> // индекс элемента, с которым будем проводить сравнение</font> '''if ''' a[mid] == key '''return ''' mid '''if ''' a[mid] < key
left = mid + 1
'''else'''
right = mid - 1
'''if ''' a[left] == key '''return ''' left '''else''' '''return ''' -1 <font color=green>// если такого элемента в массиве нет</font>
</code>
