İnterpolyasiya ilə axtarış
İnterpolyasiya ilə axtarış (ing. Interpolation search) — Artan və ya azalan sıra ilə düzülmüş massivdə verilmiş elementin tapılması alqoritmidir.
Eyni ilə ikili axtarış alqoritminin sxemi üzrə qurulur. Yeganə fərq ondan ibarətdir ki, massiv hər addımda ikiyə tən ortadan deyil, cari intervalın uclarındakı qiymətlərdən asılı olaraq xətti interpolyasiya ilə tapılmış mövqedən bölünür. Hesablamaya sərf olunan vaxt baxımından intervalın ikiyə ortadan bölunməsi ilə interpolyasıyanın hesablanması arasında fərq ciddi olmadığı üçün, bu intervalın daha böyük sürətlə yığılmasına gətirir. Massivdəki elementlərin sayı N olarsa, bir elementin mövqeyinin tapılması üçün orta hesabla
l
o
g
(
l
o
g
(
N
)
)
{\displaystyle log(log(N))}
müqayisə sərf edilər. Ən pis halda (məsələn verilənlər eksponsional xarakter daşıdıqda) tələb edilən əməliyatların sayı
O
(
N
)
{\displaystyle O(N)}
-ə çata bilər.