Умный поиск в отсортированном массиве через угадывание позиции
D = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
t = 70
l = 0
r = len(D) - 1
res = -1
while l <= r and D[l] <= t <= D[r]:
if D[l] == D[r]:
if D[l] == t:
res = l
break
else:
break
p = l + ((t - D[l]) * (r - l)) // (D[r] - D[l])
if p < l or p > r:
break
if D[p] == t:
res = p
break
elif D[p] < t:
l = p + 1
else:
r = p - 1
print(res if res != -1 else -1)#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> D = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int t = 70;
int l = 0;
int r = D.size() - 1;
int res = -1;
while (l <= r && D[l] <= t && t <= D[r]) {
if (D[l] == D[r]) {
if (D[l] == t) {
res = l;
break;
} else {
break;
}
}
int p = l + ((t - D[l]) * (r - l)) / (D[r] - D[l]);
if (p < l || p > r) {
break;
}
if (D[p] == t) {
res = p;
break;
} else if (D[p] < t) {
l = p + 1;
} else {
r = p - 1;
}
}
if (res != -1) {
cout << res << endl;
} else {
cout << -1 << endl;
}
return 0;
}
Интерполяционный поиск — это улучшенная версия бинарного поиска для отсортированных массивов. Вместо деления пополам он угадывает позицию элемента по формуле линейной интерполяции.
!!! В олимпиадном программировании этот алгоритм не используется. Здесь он по просьбе одного дурика.
Представьте, что вы ищете слово в словаре. Вы не открываете его строго посередине, а прикидываете позицию по буквам. Например, если ищете "слон", откроете ближе к концу, а если "аист" — ближе к началу.
Алгоритм делает то же самое:
p = l + ((t - D[l]) * (r - l)) / (D[r] - D[l])Для массива D = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] и t = 70:
Шаг 1: l=0, r=9, D[l]=10, D[r]=100
p = 0 + ((70 - 10) * (9 - 0)) / (100 - 10) = 0 + (60 * 9) / 90 = 6
D[6] = 70 → нашли!
Ответ: индекс 6Результат: элемент 70 найден на индексе 6
Введите отсортированный равномерный массив и число для поиска: