Veri Yapısı - Enterpolasyon Araması
İnterpolasyon araması, ikili aramanın geliştirilmiş bir çeşididir. Bu arama algoritması, gerekli değerin problama konumu üzerinde çalışır. Bu algoritmanın düzgün çalışması için, veri toplama sıralı bir biçimde ve eşit olarak dağıtılmış olmalıdır.
İkili arama, doğrusal aramaya göre zaman karmaşıklığı açısından büyük bir avantaja sahiptir. Doğrusal aramada en kötü durum karmaşıklığı Ο (n) iken, ikili arama Ο (log n) 'dir.
Hedef verilerin konumunun önceden bilinebildiği durumlar vardır. Örneğin, bir telefon rehberi olması durumunda, Morphius'un telefon numarasını aramak istiyorsak. Burada, doğrusal arama ve hatta ikili arama, 'M'den başlayan adların depolandığı bellek alanına doğrudan atlayabildiğimiz için yavaş görünecektir.
İkili Aramada Konumlandırma
İkili aramada, istenen veri bulunamazsa, listenin geri kalanı alt ve üst olmak üzere iki kısma bölünür. Arama her ikisinde de yapılır.
Veriler sıralandığında bile, ikili arama istenen verilerin konumunu araştırmak için avantaj sağlamaz.
İnterpolasyon Aramasında Konum Araştırması
Enterpolasyon araması, prob konumunu hesaplayarak belirli bir öğeyi bulur. Başlangıçta, prob konumu, koleksiyonun en ortadaki öğesinin konumudur.
Bir eşleşme olursa, öğenin dizini döndürülür. Listeyi iki bölüme ayırmak için aşağıdaki yöntemi kullanıyoruz -
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
Ortadaki öğe öğeden daha büyükse, araştırma konumu orta öğenin sağındaki alt dizide yeniden hesaplanır. Aksi takdirde, öğe, ortadaki öğenin solundaki alt dizide aranır. Bu işlem, alt dizinin boyutu sıfıra düşene kadar alt dizide de devam eder.
Enterpolasyon arama algoritmasının çalışma zamanı karmaşıklığı Ο(log (log n)) ile kıyaslandığında Ο(log n) uygun durumlarda BST.
Algoritma
Mevcut BST algoritmasının bir doğaçlaması olduğundan, konum araştırması kullanarak 'hedef' veri değeri indeksini arama adımlarından bahsediyoruz -
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.
Sözde kod
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
End Procedure
C programlama dilinde enterpolasyon aramasının uygulanması hakkında bilgi edinmek için burayı tıklayın .