- Hedef
- Hâlâ olası
- Karşılaştırılan
- Elenen
- Bulunan
Üstel arama
Üstel arama, sıralı bir listedeki bir değeri iki aşamada bulur. Önce her seferinde ikiye katlayarak 1, 2, 4, 8, 16 ve sonraki sıralara, oradaki değer hedeften küçük olmayana kadar bakar. Sonra son iki sıra arasındaki aralığı ikili aramayla tarar. Aranacak değeri seçin ve başa yakın hedeflerin neden yalnızca birkaç karşılaştırmada bulunduğunu 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. Üstel arama sıralı bir liste gerektirir, bu yüzden sıralı olmayan bir liste önce sıralanır. Değeri ve ç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
- Aranacak değeri ve çubuk sayısını seçin. Ya da kendi sayılarınızı yazın: üstel arama önce onları sıralar.
- 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.
- Başa yakın bir değeri ve sona yakın bir değeri arayın, sayıyı İkili aramada gereken kutucuğuyla karşılaştırın.
Üstel arama nasıl çalışır
1. sıradaki değere bakın. Hedeften küçükse 2. sıraya, sonra her seferinde ikiye katlayarak 4., 8. ve 16. sıralara bakın. Bir değer küçük olmadığı anda durun: hedef yalnızca bir önceki bakılan sıradan sonra ve bu sıradan önce olabilir. Bu aralığı ikili aramayla tarayın. İkiye katlama listenin sonunu aşarsa son bakılan sıradan sona kadar ikili arama yapın.
Başa yakın değerlerde hızlı, uzunluk gerekmez
i. sıradaki bir hedefe ulaşmak için ikiye katlama yaklaşık log₂ i bakış alır ve bulduğu aralıkta i'den az değer vardır; bu yüzden ikili arama yaklaşık log₂ i bakış daha alır. Toplamda yaklaşık 2 log₂ i eder ve bu, listenin uzunluğuna değil hedefin nerede olduğuna bağlıdır. Başa yakın hedefler sade ikili aramadan daha hızlı bulunur; sona yakın hedefler ise yaklaşık iki katına kadar daha pahalıdır. Listenin uzunluğuna hiç ihtiyaç duymadığı için ölçülemeyecek kadar uzun ya da sonu bilinmeyen listelerde de çalışır.
Sık sorulan sorular
Üstel arama nasıl çalışır?
Sıralı bir listede, oradaki değer hedeften küçük olmayana kadar 1, 2, 4, 8 ve sonraki sıraları kontrol eder. Bu durumda hedef yalnızca son kontrol edilen iki sıra arasında olabilir ve bu aralıkta yapılan ikili arama onu bulur.
Üstel arama ikili aramadan daha hızlı mı?
Hedef listenin başına yakınsa evet: i. sıradaki bir hedef, listenin uzunluğu ne olursa olsun yaklaşık 2 log₂ i karşılaştırma gerektirir. Hedef sona yakınsa sade ikili arama, yaklaşık iki kata kadar daha hızlıdır.
Ne için kullanılır?
Uzunluğu bilinmeyen ya da sınırsız listelerde, örneğin bir veri akışında veya sonsuz bir dizide arama yapmak ve bir sonraki eşleşmenin genellikle yakında olduğu sıralı parçaları birleştirmek için. Timsort'un dörtnala (galloping) modu da aynı ikiye katlama fikrini kullanır.
Neden üstel deniyor?
Çünkü kontrol ettiği sıralar üstel olarak büyür: 1, 2, 4, 8, 16; her biri bir öncekinin iki katı. İkiye katlamalı arama ya da dörtnala arama (galloping search) olarak da bilinir.
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