Yoklama
Hâlâ olası
İkili aramada gereken

  • Hedef
  • Hâlâ olası
  • Karşılaştırılan
  • Elenen
  • Bulunan

Enterpolasyon araması hakkında daha fazla

Enterpolasyon araması

Enterpolasyon araması, sıralı bir listede bir değeri telefon rehberini açar gibi arar: T ile başlayan bir isim için rehberi ortadan değil, sona yakın bir yerden açarsınız. Hedefin sırasını kalan kısmın iki ucundaki değerlerden tahmin eder. Değeri ve değerlerin dağılımını seçin, yoklamaları adım adım izleyin ve tahminin ikili aramayı ne zaman geçtiğini, ne zaman geçemediğini görün. Aramayı izlemek için Oynat'a, her seferinde bir adım ilerlemek için Adım ve Geri'ye basın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Kesikli çizgi aradığınız değeri gösterir, gölgeli kısım ise değerin hâlâ bulunabileceği yerdir. Enterpolasyon araması sıralı bir liste gerektirir, bu yüzden sırasız bir liste önce sıralanır. Değeri, değerlerin nasıl dağıldığını, çubuk sayısını seçin ya da kendi sayılarınızı yazın. Tahta seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. Aranacak değeri, değerlerin nasıl dağıldığını ve çubuk sayısını seçin. Ya da kendi sayılarınızı yazın: enterpolasyon araması onları önce sıralar.
  2. Oynat'a basın ya da her seferinde bir adım ilerlemek için Adım ve Geri'yi kullanın. Aramanın herhangi bir yerine atlamak için adım kaydırıcısını sürükleyin.
  3. Dağılım'ı Düzgün, Rastgele boşluklar ve Çarpık arasında değiştirin ve Yoklama ile İkili aramada gereken değerlerini karşılaştırın.

Enterpolasyon araması nasıl çalışır

Sıralı listenin hedefi hâlâ içerebilecek kısmının ilk ve son değerine bakın. Hedef, diyelim ki ilk değerden son değere giden yolun %40'ındaysa, yolun %40'ındaki sırayı yoklayın. Oradaki değer hedefse işiniz bitmiştir. Daha küçükse yalnızca ondan sonraki sıralar kalır; daha büyükse yalnızca ondan öncekiler. Kalan kısımda yeniden tahmin edin. Hedef ilk değerden küçük ya da son değerden büyükse listede yoktur.

Tahmin ne zaman işe yarar

Değerler 10, 20, 30 diye giden bir dizi gibi düzgün dağılmışsa ilk tahmin hedefe ya da çok yakınına düşer ve arama ortalama yaklaşık log₂(log₂ n) yoklama gerektirir: bir milyar değer için yaklaşık 5, ikili aramada ise 30. Değerler 1, 2, 3, 4, 1000 gibi kümelenirse tahminler sürekli yanlış yere düşer ve her yoklama belki yalnızca bir değeri eler; bu yüzden en kötü durum n yoklamadır. İkili arama hiçbir zaman yaklaşık log₂ n'den daha kötü olmaz.

Sık sorulan sorular

Enterpolasyon araması nasıl çalışır?

Sıralı bir listede hedefin nerede olması gerektiğini kalan kısmın ilk ve son değerinden tahmin eder, o sırayı yoklar ve yalnızca doğru taraftaki kısmı tutar. Ortadan daha akıllıca bir tahminle çalışan ikili arama gibidir.

Enterpolasyon araması ikili aramadan daha hızlı mı?

Düzgün dağılmış değerlerde evet: ortalama yaklaşık log₂ n yerine yaklaşık log₂(log₂ n) yoklama. Düzensiz dağılmış değerlerde çok daha yavaş olabilir, n yoklamaya kadar çıkabilir; ikili arama ise hiçbir zaman yaklaşık log₂ n'den fazlasına ihtiyaç duymaz.

Neden yavaş olabilir?

Çünkü tahmin, değerlerin düzgün arttığını varsayar. Değerlerin çoğu küçük ve birkaçı çok büyükse küçük bir hedef için tahmin tekrar tekrar başa yakın düşer ve her seferinde yalnızca bir iki değeri eler.

Enterpolasyon araması nerede kullanılır?

Anahtarların neredeyse düzgün dağıldığı ve yoklamaların pahalı olduğu yerlerde; örneğin diskteki kayıtları sayısal kimliğe ya da hash değerine göre ararken. Birçok sistem, en kötü durumu iyi tutmak için onu ikili aramayla birleştirir.

Sayılarım bir yere gönderiliyor mu?

Hayır. Arama tarayıcınızda çalışır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git