Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Arama performansını optimize etmek amacıyla erişim sıklıklarına göre öğe düzenini dinamik olarak değiştiren veya tahmini konuma doğrudan atlayan tekniklerdir.
Arama Teknikleri, standart doğrusal ve ikili arama yöntemlerini daha verimli kılmak amacıyla geliştirilmiş optimize arama şemalarıdır. Bu başlık altında özellikle üç temel yöntem incelenir.
Olasılıksal Arama (Probability Search), sık aranan elemanları listenin başına yakın tutarak doğrusal aramanın ortalama adım sayısını azaltır. Kendini Düzenleyen Arama (Self-Organizing Search) ise benzer mantıkla, aranan elemanı doğrudan en başa taşıyan "Move-To-Front" (MTF) veya bir önceki elemanla yer değiştiren "Transpose" tekniklerini kullanır.
İnterpolasyon Araması (Interpolation Search), sıralı ve yaklaşık düzgün dağılıma sahip dizilerde hedef değere göre bir tahmin indeksi hesaplayarak doğrudan hedefe en yakın noktaya atlar. Bu yönüyle ikili aramadan daha hızlı, O(log log n) zamanda çalışabilir.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function interpolationSearch(arr: number[], target: number): number {2 let low = 0;3 let high = arr.length - 1;45 while (arr[low] <= target && target <= arr[high] && arr[low] !== arr[high]) {6 const pos = low + Math.floor(7 ((high - low) * (target - arr[low])) / (arr[high] - arr[low])8 );910 if (arr[pos] === target) return pos;11 if (arr[pos] < target) {12 low = pos + 1;13 } else {14 high = pos - 1;15 }16 }1718 if (arr[low] === target) return low;19 return -1;20}2122function selfOrganizingSearchMoveToFront(arr: T[], target: T): number { 23 const idx = arr.indexOf(target);24 if (idx > 0) {25 // Bulunan elemanı en başa (index 0) taşı26 const item = arr.splice(idx, 1)[0];27 arr.unshift(item);28 return 0;29 }30 return idx;31}Sıralı dizi elemanlarını ve aranacak hedefi girin. Örnek: 10,20,30,40,50,60,70,80; 60
Sıralı dizi elemanlarını ve aranacak hedefi girin. Örnek: 10,20,30,40,50,60,70,80; 60
En İyi Durum: O(1)
Ortalama Durum: O(log log n)
En Kötü Durum: O(n)
O(1) - Giriş boyutu ne olursa olsun, algoritma her zaman aynı sürede çalışır.
Arama Teknikleri (Search Techniques) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: