Bölüm 3: Arama Algoritmaları

3.1Arama problemi

Arama, bilgisayar biliminin en eski ve en yaygın problemlerinden biridir. Kullanıcı adını denetleyen giriş ekranı, ürün fiyatını bulan kasa programı ve yazım denetimi yapan metin düzenleyici aynı temel işi yapar. Bu işin ne kadar hızlı yapıldığı, programın bütün başarımını belirleyebilir. Arama bir döngünün içinde milyonlarca kez çalışıyorsa, her aramadan kazanılan birkaç mikrosaniye toplamda saatlere dönüşür.

3.1.1Problemin tanımı

Arama algoritmaları bir veri kümesinde istenen değeri bulmak için kullanılır. Algoritma verileri bir arama ölçütüne göre tarar ve ölçüte uyan öğeyi bulmaya çalışır. Ölçüt çoğunlukla bir anahtardır (key). Öğrenci kayıtlarında anahtar öğrenci numarası, sözlükte kelimenin kendisi, telefon rehberinde kişinin adıdır. Bu notta problemi en yalın hâliyle ele alıyoruz: öğeler bir tam sayı dizisindedir ve anahtar öğenin kendi değeridir. Gerçek uygulamalarda dizinin her hücresi bir kayıt tutar ve karşılaştırma kaydın anahtar alanıyla yapılır; algoritmaların mantığı değişmez.

Tanımın iki ayrıntısı önemlidir. Birincisi, çıktı değerin kendisi değil, konumudur. Aranan değer zaten bilinir; asıl soru onun dizide nerede durduğudur. Konum bilinince o hücredeki kaydın diğer alanlarına da ulaşılabilir. İkincisi, başarısız arama da geçerli bir sonuçtur. Java'da dizi indisleri 0'dan başladığı için −1 hiçbir geçerli indisle karışmaz ve “bulunamadı” anlamını güvenle taşır.

Dizide aranan değer birden çok kez geçiyorsa tanım, bunlardan herhangi birinin indisini kabul eder. Hangi eşleşmenin döneceği algoritmaya bağlıdır. Doğrusal arama baştan taradığı için ilk eşleşmeyi bulur; ikili arama ise ortadan başladığı için rastgele görünen bir eşleşmeyi verebilir. İlk ya da son eşleşme özellikle isteniyorsa algoritmanın buna göre uyarlanması gerekir.

3.1.2Maliyet ölçüsü: yoklama sayısı

Bir arama algoritmasının ne kadar hızlı olduğunu saniyeyle ölçmek yanıltıcıdır, çünkü süre işlemciye, dile ve derleyiciye göre değişir. Bunun yerine, algoritmanın doğasını yansıtan bir işlem sayılır. Arama algoritmalarında süreyi belirleyen işlem, aranan değerin dizideki bir öğeyle karşılaştırılmasıdır.

Yoklama sayısını seçmenin gerekçesi basittir. Döngü sayaçlarını artırmak, sınırları güncellemek gibi diğer işler her yoklamaya sabit sayıda eşlik eder. Dolayısıyla toplam süre, yoklama sayısıyla bir sabitin çarpımı kadardır ve büyüme mertebesi aynı kalır. Bir hash tablosunda yoklama, bir kovaya bakıp oradaki anahtarı aranan anahtarla karşılaştırmaktır; tanım oraya da aynen uyar.

Maliyet aynı n için bile girdiden girdiye değişir. Aranan değer dizinin başındaysa doğrusal arama hemen biter, sonundaysa bütün diziyi dolaşır. Bu yüzden her algoritma için üç durum ayrı ayrı incelenir. En iyi durum (best case) en az yoklama gerektiren girdidir. En kötü durum (worst case) en çok yoklama gerektiren girdidir ve algoritmanın verebileceği bir güvenceyi gösterir. Ortalama durum (average case) ise girdilerin belli bir olasılık dağılımına göre geldiği varsayılarak hesaplanan beklenen yoklama sayısıdır. En kötü durum çoğu zaman en önemli ölçüdür, çünkü “hiçbir girdide bundan yavaş olmaz” demeyi sağlar.

3.1.3Arama algoritmalarının çeşitleri

Farklı arama algoritmaları farklı ilkelerle çalışır ve verinin farklı özelliklerini önkoşul olarak ister. Bir algoritma ne kadar çok önkoşul isterse, o önkoşul sağlandığında o kadar hızlı çalışma eğilimindedir. Tablo 3.1 bu notta incelenen altı yöntemi önkoşulları ve ilkeleriyle özetler.

Tablodaki önkoşullar iki gruba ayrılır. Doğrusal arama hiçbir şey istemez; dizi sırasız, hatta bir bağlı liste bile olabilir. Hash ile arama verinin önceden özel bir yapıya, hash tablosuna yerleştirilmesini ister. Geriye kalan dört yöntem sıralı dizi ister. Sıralı dizinin sağladığı bilgi şudur: bir hücredeki değer aranandan küçükse, aranan o hücrenin solunda olamaz. Bu tek karşılaştırma, dizinin büyük bir kısmını bir kerede elemeyi sağlar. İkili, ara değer, atlayarak ve üstel arama bu bilgiyi farklı biçimlerde kullanır.

Sıralı olma önkoşulunun bir bedeli vardır. Diziyi sıralamak en iyi karşılaştırmalı algoritmalarla O(n log n) zaman alır. Tek bir arama için diziyi sıralamak, doğrudan doğrusal arama yapmaktan pahalıdır. Sıralama ancak aynı dizide çok sayıda arama yapılacaksa kendini amorti eder.

3.2Doğrusal arama

Doğrusal arama, akla gelen ilk ve en sade yöntemdir. Önkoşul istemediği için her durumda kullanılabilir. Bu genellik, hızdan ödün vermenin karşılığıdır.

3.2.1Fikir

Doğrusal arama (linear search) listedeki her öğeyi sırayla kontrol eder. Bir alışveriş listesindeki ürünleri tek tek gözden geçirmek ya da kayıp bir eşyayı bulmak için odayı köşe köşe taramak aynı fikre dayanır. Aranan değer listenin başından başlanarak her öğeyle karşılaştırılır. Eşleşme bulunursa o öğenin indisi döndürülür. Liste bitmiş ve eşleşme çıkmamışsa sonuç −1'dir.

Bazen aranan bilgiyi bulmanın en iyi yolu gerçekten tek tek bakmaktır. Dizi sırasızsa başka seçenek de yoktur. Sırasız bir dizide herhangi bir hücreye bakmak, diğer hücreler hakkında hiçbir bilgi vermez. 33'ün aranan değil olduğunu öğrenmek, 21'in aranan olup olmadığı konusunda hiçbir şey söylemez. Dolayısıyla başarısız bir aramanın “yok” diyebilmesi için her hücreye en az bir kez bakmak zorunludur. Bu basit gözlem, sırasız veride hiçbir algoritmanın en kötü durumda n'den az yoklama yapamayacağını gösterir.

3.2.2Kod: dogrusalArama()

Doğrusal aramanın Java kodu şöyledir:

int dogrusalArama(int[] dizi, int n,
                  int aranan) {
  int i = 0;
  while (i < n && dizi[i] != aranan)
    i++;
  if (i < n)
    return i;      // bulundu: indis
  else
    return -1;     // bulunamadı
}

Metot üç parametre alır: dizi aranacak öğeleri, n dizinin kullanılan boyutunu, aranan ise aranacak değeri tutar. Dönüş değeri aranan öğenin indisidir; öğe bulunamazsa −1'dir. Boyutun ayrı bir parametre olarak verilmesi, dizinin yalnız ilk n hücresinin dolu olduğu durumları da kapsar.

int i = 0; satırı dizinin başından başlamayı sağlar. while döngüsünün koşulu iki parçalıdır: i < n dizinin sonuna gelinmediğini, dizi[i] != aranan ise o hücrede aranan değerin bulunmadığını denetler. İki koşul da doğru olduğu sürece döngü gövdesi çalışır ve i bir artar. Döngü iki nedenden biriyle durur: ya i, n'ye ulaşmıştır, ya da dizi[i] aranana eşittir. Döngüden sonraki if bu iki durumu ayırır. i < n doğruysa döngü bir eşleşme yüzünden durmuştur ve i eşleşmenin indisidir. Yanlışsa dizi baştan sona taranmış, eşleşme çıkmamıştır; metot −1 döndürür.

Koşulların sırası önemlidir. Java'nın && işleci kısa devre çalışır: sol taraf yanlışsa sağ taraf hiç hesaplanmaz. i == n olduğunda i < n yanlıştır ve dizi[n] ifadesine hiç erişilmez. Koşullar ters yazılsaydı, yani dizi[i] != aranan && i < n denseydi, başarısız bir aramanın son adımında dizi[n] okunmaya çalışılır ve ArrayIndexOutOfBoundsException fırlatılırdı.

3.2.3En iyi ve en kötü durum

Algoritmanın davranışı, on öğeli sırasız bir örnek dizi üzerinde şöyle görülür:

dizi = {33, 21, 12, 7, 8, 1, 3, 44, 56, 18}, n = 10

En kötü durum iki farklı girdiyle ortaya çıkar: aranan dizide yoksa ya da yalnız son hücrede bulunuyorsa. İkisinde de n değer karşılaştırması yapılır. Aradaki tek fark, döngünün son sınamasıdır. Aranan son hücredeyse döngü i = n − 1 konumunda eşleşmeyle durur. Aranan yoksa bir tur daha döner ve i = n olunca sınır koşuluyla durur.

3.2.4Kod izleme: ortalama bir arama

En iyi ve en kötü durum iki uçtur. Tipik bir arama için aynı dizide 1 aranıyor. 1, dizinin ortasına yakın bir yerde, 5. indistedir. Tablo 3.2, dogrusalArama(dizi, 10, 1) çağrısında döngü koşulunun her sınanışını gösterir.

Altıncı sınamada dizi[5] = 1 aranana eşittir; while koşulu yanlış olur ve döngüden çıkılır. Ardından i = 5 < n doğrudur ve metot 5 döndürür. Toplam 6 değer karşılaştırması yapılmıştır. Genel kural açıktır: k indisindeki bir öğe k + 1 karşılaştırmayla bulunur.

3.2.5Karmaşıklık ve değerlendirme

En iyi ve en kötü durumun maliyeti kolayca okunur: biri 1, öteki n karşılaştırmadır. Ortalama durum için bir varsayım gerekir. En yaygın varsayım, aramanın başarılı olduğu ve aranan değerin her konumda bulunma olasılığının eşit olduğudur.

n = 10 için ortalama 11/2 = 5,5 karşılaştırmadır. Sonuç sezgiyle de uyumludur: aranan öğe ortalamada dizinin ortasındadır, dolayısıyla yaklaşık yarısına bakılır. Başarısız aramada ise her zaman n karşılaştırma yapılır. Tablo 3.3 üç durumu bir araya getirir.

Ortalama durumun da O(n) olması önemli bir sonuçtur. Ortalama maliyet en kötü durumun yalnız yarısıdır; yarıya inmek mertebeyi değiştirmez. Dizi on kat büyürse ortalama arama da on kat uzar. Ek bellek açısından durum iyidir: algoritma yalnız i değişkenini kullanır, ek bellek O(1)'dir.

Doğrusal aramanın avantajları şöyle sıralanabilir:

• Kodlaması ve anlaşılması kolaydır; karmaşık bir veri yapısı gerektirmez.
• Ön hazırlık istemez: dizinin sıralı olması gerekmez.
• Küçük veri kümelerinde idealdir. Kişisel bir rehber listesinde bir numara aramak için daha karmaşık bir yönteme gerek yoktur.
• Bağlı liste gibi yalnız sırayla erişilebilen yapılarda da çalışır. İkili arama bir bağlı listede verimli çalışamaz, çünkü ortadaki öğeye ulaşmak bile O(n) adım ister.

Dezavantajları da açıktır:

• Büyük veride yavaştır. 10⁶ öğeli bir dizide başarılı bir arama ortalama 500.000 karşılaştırma yapar.
• Dizi sıralı olsa bile bu bilgiden yararlanmaz. Sıralı bir dizide aranandan büyük bir değere rastlandığında arama durdurulabilirdi; temel algoritma bunu yapmaz.
• Aynı dizide çok sayıda sorgu yapılacaksa diziyi bir kez sıralayıp ikili arama kullanmak çok daha ucuzdur.

3.2.6Bekçili doğrusal arama

Doğrusal aramanın döngüsüne dikkatle bakınca her turda iki karşılaştırma yapıldığı görülür: i < n ve dizi[i] != aranan. Bunlardan yalnız ikincisi aramanın asıl işidir. Birincisi, dizinin dışına taşmamak için konmuş bir güvenlik denetimidir. Bu denetimi döngüden çıkarmanın zekice bir yolu vardır.

Bekçiye “gözcü” de denir; metodun adı gozcuIleAra buradan gelir:

int gozcuIleAra(int[] dizi, int n,
                int aranan) {
  int sonEleman = dizi[n - 1];
  dizi[n - 1] = aranan;     // bekçi
  int i = 0;
  while (dizi[i] != aranan)
    i++;
  dizi[n - 1] = sonEleman;  // geri koy
  if (i < n - 1 || sonEleman == aranan)
    return i;
  return -1;
}

Metot önce son öğeyi sonEleman değişkenine kaydeder ve son hücreye aranan değeri yazar. Bu andan sonra dizide aranan değerin en az bir kopyası vardır. Döngü artık yalnız dizi[i] != aranan koşulunu sınar; i sınırı aşamaz, çünkü en geç n − 1 konumunda eşleşme bulunur. Döngü bitince son hücreye eski değeri geri yazılır, dizi ilk hâline döner.

Son adım dikkat ister. Döngünün durduğu yer iki anlama gelebilir. i < n − 1 ise eşleşme bekçiden önce, gerçek bir öğede bulunmuştur. i == n − 1 ise döngü bekçide durmuştur. Bu durumda da aranan değer bulunmuş olabilir: dizinin gerçek son öğesi aranana eşitse. Bu yüzden if koşulunun ikinci parçası sonEleman == aranan'dır. İki koşuldan biri doğruysa i döner, ikisi de yanlışsa −1.

Kazanç sayılarla şöyledir. Klasik döngü, başarısız bir aramada n değer karşılaştırması ve n + 1 sınır sınaması yapar; toplam yaklaşık 2n karşılaştırma eder. Bekçili döngü n değer karşılaştırması yapar. Döngüden sonra iki karşılaştırma daha gelir: i < n − 1 ve sonEleman == aranan. Toplam yaklaşık n + 2'dir. Karşılaştırma sayısı neredeyse yarıya iner, ama mertebe yine O(n)'dir. Bu, sabit çarpanı küçülten bir iyileştirmedir.

3.2.7Kod izleme: gozcuIleAra()

Bekçili aramanın başarısız bir aramadaki izlemesi: dizi = [7, 3, 9, 4, 6], n = 5, aranan 5. 5 dizide yoktur.

İkinci if koşulunun neden gerektiğini farklı bir örnek gösterir: dizi = [12, 5, 9, 20, 7] ve aranan 7. Burada aranan değer gerçekten son hücrededir. Bekçi olarak yine 7 yazılır, döngü i = 4'te durur. i < n − 1 yanlıştır, ama sonEleman == aranan doğrudur ve metot doğru olarak 4 döndürür. Bu koşul olmasaydı dizinin gerçek son öğesi hiçbir zaman bulunamazdı.

3.3İkili arama

Doğrusal arama her yoklamada dizinin yalnız bir hücresini eler. Dizi sıralıysa tek bir yoklama çok daha fazlasını söyler. Ortadaki öğe aranandan küçükse, sıralılık gereği onun solundaki bütün öğeler de aranandan küçüktür ve hiçbiri aranan olamaz. Tek yoklama dizinin yarısını eler. İkili arama bu gözlem üzerine kurulur.

3.3.1Fikir

Kütüphanede kitap aramak iyi bir benzetmedir. Kitaplar yazarın soyadına göre alfabetik sıralanmıştır. Bütün rafları baştan tek tek gezmek yerine önce orta bölüme gidilir. Aranan kitap ortadaki rafın solunda kalıyorsa sol taraftaki raflarda, sağında kalıyorsa sağ taraftaki raflarda aramaya devam edilir. Kalan bölümde de yine ortaya gidilir. Her karşılaştırma, aranması gereken kısmı yarıya indirir.

İkili aramanın iki önkoşulu vardır. Birincisi, dizi sıralı olmalıdır; bu not boyunca sıralı derken küçükten büyüğe sıralı kastediliyor. İkincisi, öğelere indisle O(1) sürede erişilebilmelidir. Bu ikinci koşul dizide sağlanır, bağlı listede sağlanmaz. Bağlı listede ortadaki öğeye ulaşmak için baştan itibaren yarı liste yürümek gerekir. Bu durumda tek bir “orta” hesabı bile doğrusal arama kadar pahalı olur.

3.3.2İkili arama neden hızlı?

İkili aramanın gücü, aralığın her adımda yarıya inmesinden gelir. 1000 öğeli bir listede doğrusal arama ortalama 500 kontrol yapar. İkili arama ise en fazla 10 adımda aramayı tamamlar. Aralık boyları her karşılaştırmadan sonra şöyle küçülür:

1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1

Dizide on aralık boyu vardır ve her aralık boyu bir karşılaştırmaya karşılık gelir: toplam 10 karşılaştırma. Yarıya inerken kesirli kısım atılır, çünkü ortadaki öğe karşılaştırıldıktan sonra artık aralıkta değildir. Örneğin 125 öğeli bir aralıkta ortadaki öğe çıkınca iki yanda 62'şer öğe kalır.

Bu küçülmenin ne kadar etkili olduğu büyük n değerlerinde ortaya çıkar. Tablo 3.4 iki yöntemin en kötü durumdaki karşılaştırma sayılarını yan yana koyar.

İkili arama en fazla ⌊log₂ n⌋ + 1 karşılaştırma yapar. Bir milyar öğeli bir dizide 30 karşılaştırma yeterlidir. Veri 1000 kat büyüdüğünde ikili aramaya yalnız yaklaşık 10 adım eklenir, çünkü 2¹⁰ = 1024 ≈ 1000'dir. Doğrusal arama ise 1000 kat yavaşlar. Bu tür büyümeye logaritmik (logarithmic) büyüme denir.

3.3.3Kod: yinelemeli ikiliArama()

İkili aramanın döngüyle yazılmış (yinelemeli) Java kodu şöyledir:

int ikiliArama(int[] dizi, int n, int aranan) {
  int bas = 0, son = n - 1;
  while (bas <= son) {
    int orta = (bas + son) / 2;
    if (aranan < dizi[orta])
      son = orta - 1;      // sol yarı
    else if (aranan > dizi[orta])
      bas = orta + 1;      // sağ yarı
    else
      return orta;         // bulundu
  }
  return -1;
}

bas ve son, arama yapılacak aralığın alt ve üst sınırlarıdır; ikisi de aralığa dahildir. Başlangıçta aralık bütün dizidir: bas = 0, son = n − 1. while (bas <= son) koşulu aralık boş olmadığı sürece döngüyü sürdürür. bas == son olduğunda aralıkta tek öğe vardır ve bu öğe de sınanmalıdır; koşulun <= olması bu yüzdendir.

Her turda orta, aralığın ortasındaki öğenin indisi olarak hesaplanır. Tam sayı bölmesi kesirli kısmı attığı için aralıkta çift sayıda öğe varsa iki ortadan soldaki seçilir. Ardından üç yol vardır. Aranan dizi[orta]'dan küçükse aranan, varsa, ortanın solundadır; son = orta − 1 ile sol yarıya geçilir. Aranan büyükse bas = orta + 1 ile sağ yarıya geçilir. Eşitse orta döndürülür. Döngü bir eşleşme bulunmadan biterse aralık boşalmıştır (bas > son) ve metot −1 döndürür.

Sınırların orta − 1 ve orta + 1 ile güncellenmesi kritiktir. Orta öğe az önce sınanmış ve aranan olmadığı anlaşılmıştır; bu yüzden yeni aralığa alınmaz. Bu kural aynı zamanda aralığın her turda en az bir öğe küçülmesini, dolayısıyla döngünün mutlaka bitmesini güvenceye alır.

3.3.4Özyinelemeli sürüm

İkili arama doğal olarak özyinelemeli bir yapıdadır: aralığın bir yarısında arama, aynı problemin daha küçük bir örneğidir. Özyinelemeli Java kodu şöyledir:

int ara(int[] dizi, int bas,
        int son, int aranan) {
  if (bas > son) return -1;  // boş aralık
  int orta = (bas + son) / 2;
  if (dizi[orta] == aranan) return orta;
  if (dizi[orta] < aranan)           // sağ yarı
    return ara(dizi, orta + 1, son, aranan);
  return ara(dizi, bas, orta - 1, aranan);
}

İlk çağrı ara(dizi, 0, n - 1, aranan) biçimindedir. Metot önce taban durumunu denetler: bas > son ise aralık boştur ve −1 döner. Değilse orta öğe hesaplanır ve aranana eşitse indisi döner. Aksi hâlde aranan büyükse sağ yarıda, küçükse sol yarıda aynı metot yeniden çağrılır ve onun sonucu olduğu gibi döndürülür. Yinelemeli sürümdeki bas ve son güncellemelerinin yerini burada yeni çağrının parametreleri alır.

Algoritma tasarımı açısından ikili arama, böl ve fethet (divide and conquer) yaklaşımının en sade örneğidir. Böl adımı ortadaki öğeyi seçmektir. Fethet adımı yalnız bir yarıda devam etmektir; öteki yarıya hiç dokunulmaz. Birleştir adımı yoktur, çünkü alt problemin cevabı doğrudan problemin cevabıdır. Tek dallı olduğu için bu yaklaşıma azalt ve fethet (decrease and conquer) de denir. Maliyet şu özyineleme bağıntısıyla anlatılır:

T(n) = T(n/2) + 1

Bağıntı, n öğeli bir aramanın bir karşılaştırma ile n/2 öğeli bir arama yapmasını ifade eder. Çözümü T(n) = O(log n)'dir.

İki sürüm aynı karşılaştırmaları yapar, ama bellek kullanımları farklıdır. Yinelemeli sürüm yalnız birkaç değişken kullanır: ek bellek O(1)'dir. Özyinelemeli sürümde her çağrı çağrı yığınında bir çerçeve açar ve çağrılar iç içe en fazla ⌊log₂ n⌋ + 1 derinliğe iner. Ek bellek O(log n)'dir. Bu değer küçüktür; bir milyar öğede bile 30 çerçeve yeter. Yine de yinelemeli sürüm hem bellekte hem de çağrı maliyetinde daha hafiftir ve pratikte daha çok tercih edilir.

3.3.5İkili arama ve dengeli ikili arama ağacı

İkili aramanın yaptığı karşılaştırmalar bir ağaç biçiminde çizilebilir. Bu çizim, algoritmanın neden en fazla ⌊log₂ n⌋ + 1 adım attığını gözle görmeyi sağlar. Örnek olarak 15 öğeli bir sıralı dizi alınsın:

5, 11, 12, 14, 15, 18, 19, 21, 23, 25, 27, 28, 30, 32, 37

Bu ağaç bir ikili arama ağacıdır: her düğümün sol alt ağacındaki değerler düğümden küçük, sağ alt ağacındakiler büyüktür. Üstelik mümkün olan en dengeli ağaçtır; her düzey tamamen doludur. İkili arama, sıralı dizi üzerinde bu en iyi ağaçta kökten aşağı yürümekle aynı şeydir. Bir ağaçta arama maliyeti, aranan düğümün derinliğine bir eklenerek bulunur. En kötü durum ağacın yüksekliğine bağlıdır. n düğümlü dengeli bir ağacın yüksekliği ⌊log₂ n⌋'dir. Ağaç dengesiz kurulsaydı, örneğin her düğümün yalnız sağ çocuğu olsaydı, yükseklik n − 1 olurdu ve arama doğrusal aramaya dönerdi.

3.3.6Örtük ağaçta arama

Ağacın bellekte kurulması gerekmez. Sıralı dizi ağacın kendisidir; orta hesabı ağacı örtük olarak gezer. Bir düğümün sol çocuğu, sol yarı aralığın ortasıdır; sağ çocuğu sağ yarının ortasıdır. İkinci bir sıralı dizi bunu gösterir. Dizi yine 15 öğelidir:

1, 3, 5, 6, 7, 8, 11, 14, 16, 18, 20, 22, 23, 25, 27

Ağaç bakışı başarısız aramayı da açıklar. Aranan değer dizide yoksa arama bir yaprağa kadar iner ve yaprağın boş bir çocuğuna gitmeye çalışır. Bu boş çocuk, aranan değerin sırayı bozmadan ekleneceği aralığa karşılık gelir. Örneğin bu dizide 19 aranırsa yol 14 → 22 → 18 → 20 olur. 19, 20'den küçük olduğu için 20'nin sol çocuğuna gidilmek istenir, ama o çocuk boştur. 19, 18 ile 20 arasına girecekti.

3.3.7En iyi ve en kötü durum

Kodun iki ucu dokuz öğeli bir dizide sayılabilir:

dizi = {5, 7, 10, 17, 23, 34, 55, 67, 99}, n = 9

Bu dizide en kötü durum aslında 4 karşılaştırmadır: ⌊log₂ 9⌋ + 1 = 4. 54 aramasının 3 adımda bitmesi, aranan değerin ağacın sığ bir kolunda başarısız olmasındandır. Örneğin 99 aranırsa yoklanan indisler 4, 6, 7, 8 olur ve 4 karşılaştırma yapılır. Sınır en kötü durumu verir; her başarısız arama bu sınıra ulaşmaz.

3.3.8Kod izleme: ikiliArama(dizi, 9, 47)

Başarılı bir aramanın değişken değerleriyle izlemesi aşağıdadır. Dizi {0, 4, 7, 10, 14, 23, 45, 47, 53}, aranan 47'dir.

Birinci turda bas ≤ son doğrudur; orta (0 + 8)/2 = 4 olarak hesaplanır ve dizi[4] = 14'tür. 47 daha büyük olduğu için sol kısım elenir: bas = 5. İkinci turda orta (5 + 8)/2 = 6'dır, dizi[6] = 45 yine küçüktür: bas = 7. Üçüncü turda orta (7 + 8)/2 = 7'dir ve dizi[7] = 47 aranana eşittir; metot 7 döndürür. Dokuz öğede 3 karşılaştırma yapılmıştır. Bu dizi için sınır ⌊log₂ 9⌋ + 1 = 4'tür.

Karşılaştırma sayımında bir ayrıntı vardır. Koddaki her turda aranan < dizi[orta] ve gerekirse aranan > dizi[orta] olmak üzere iki karşılaştırma yazılıdır. Ama ikisi de aynı hücreye bakar; yoklama sayısı bir artar. Notta “karşılaştırma” sayılırken bir orta öğeye bakış bir karşılaştırma kabul edilir. Java'da tam sayılar için iki karşılaştırma yerine tek bir Integer.compare çağrısı da kullanılabilir.

3.3.9Karmaşıklık

İkili aramanın en kötü durumu kesin olarak şöyle ifade edilir.

Teorem, T(n) = T(n/2) + 1 bağıntısının çözümüyle de uyumludur. Bağıntı açılırsa T(n) = T(n/2^k) + k elde edilir. n/2^k = 1 olduğunda, yani k = log₂ n için alt problem sabit maliyetlidir. Toplam log₂ n mertebesindedir.

Ortalama durumun da O(log n) olması ağaç bakışından anlaşılır. Dengeli bir ağaçta düğümlerin yaklaşık yarısı yapraktır ve yaprakların derinliği en büyük derinliktir. Rastgele seçilen bir öğe büyük olasılıkla alt düzeylerdedir. 15 öğeli örnekte ortalama 3,27, en kötü durum 4 karşılaştırmaydı; ikisi arasındaki fark sabittir.

Tablonun son satırı ikili aramanın gizli bedelidir. Dizi sırasızsa önce sıralanmalıdır ve bu O(n log n) sürer. Sıralama bir kez yapılır, aramalar defalarca. k sorgu için iki yolun maliyeti şöyledir:

• Doğrusal arama: toplam O(k · n).
• Bir kez sırala, sonra ikili arama: toplam O(n log n + k log n).

k küçükse, örneğin tek sorgu varsa, doğrusal arama daha ucuzdur. k, log n mertebesini aştığında sıralamanın maliyeti kendini çıkarır ve k büyüdükçe fark hızla açılır.

3.3.10Uygulama ayrıntıları

İkili arama fikir olarak basittir, ama doğru yazmak şaşırtıcı ölçüde zordur. Knuth, ilk ikili arama yayınının 1946'da çıktığını, hatasız bir sürümün ise ancak 1962'de yayımlandığını aktarır. Hataların çoğu dört ayrıntıda toplanır.

Orta hesabında taşma. (bas + son) / 2 ifadesi matematik olarak doğrudur, ama Java'da int en fazla 2³¹ − 1 = 2.147.483.647 değerini tutar. bas + son bu sınırı aşarsa toplam negatif bir sayıya döner ve orta negatif olur. İki indisin toplamının bu sınırı aşması için dizinin yaklaşık bir milyar (2³⁰) öğeyi geçmesi gerekir. Bu sınır eskiden uzak görünüyordu; bugün büyük dizilerde ve dosya konumlarında gerçek bir risktir. Java kütüphanesinin Arrays.binarySearch metodunda bu hata yıllarca fark edilmeden kalmış ve 2006'da düzeltilmiştir. Güvenli yazımlar şunlardır:

bas + (son - bas) / 2  ya da  (bas + son) >>> 1

Birincisi farkı böler ve hiçbir zaman taşmaz. İkincisi, taşmış toplamı işaretsiz sağa kaydırma ile yeniden doğru değere çevirir. Örneğin bas = 2.000.000.000 ve son = 2.100.000.000 için (bas + son) / 2 ifadesi −97.483.648 verir; iki güvenli yazım da doğru sonuç olan 2.050.000.000'i verir.

Sınırların güncellenmesi. son = orta ya da bas = orta yazmak aralığı küçültmeyebilir. bas == son iken aranan dizi[orta]'dan küçükse son = orta ataması aralığı değiştirmez ve döngü sonsuza dek döner. Orta öğe zaten denetlendiği için sınırlar ±1 ile güncellenmelidir.

Tekrarlı öğeler. Eşitlikte hemen dönmek, eşleşmelerden herhangi birini verir. {2, 4, 4, 4, 4, 7, 9, 12} dizisinde 4 aranırsa yinelemeli ikili arama ilk turda 3. indise bakar ve 3 döndürür; oysa ilk 4, 1. indistedir. İlk konum isteniyorsa eşitlikte sonuç kaydedilir ve son = orta − 1 ile sola devam edilir.

Java kütüphanesi. Arrays.binarySearch(dizi, x) sıralı bir dizide ikili arama yapar. Değer bulunursa indisini döndürür; tekrarlı öğelerde hangisinin döneceği belirsizdir. Bulunamazsa −(ekleme noktası) − 1 döndürür. Ekleme noktası, x'in sırayı bozmadan ekleneceği indistir. Dönüş değerinin her zaman negatif olması bulunamadı bilgisini, mutlak değeri ise konumu taşır. Örneğin {2, 4, 4, 4, 4, 7, 9, 12} dizisinde 5 aranırsa ekleme noktası 5'tir ve metot −5 − 1 = −6 döndürür. “−1” yerine yalnız “−(ekleme noktası)” döndürülseydi, ekleme noktası 0 olan bir değer için dönüş 0 olur ve bulunmuş bir öğeyle karışırdı.

3.3.11Tekrarlı öğelerde ilk konum

Tekrarlı öğe içeren sıralı bir dizide aranan değerin ilk konumunu bulan ikili arama şöyle yazılır:

int ilkKonum(int[] dizi, int aranan) {
  int bas = 0, son = dizi.length - 1, sonuc = -1;
  while (bas <= son) {
    int orta = bas + (son - bas) / 2;
    if (dizi[orta] == aranan) {
      sonuc = orta;      // kaydet,
      son = orta - 1;    // solda ara
    } else if (dizi[orta] < aranan)
      bas = orta + 1;
    else
      son = orta - 1;
  }
  return sonuc;
}

Kod, yinelemeli ikili aramadan iki noktada ayrılır. Birincisi, sonuc değişkeni bugüne kadar bulunan en soldaki eşleşmeyi tutar; başlangıç değeri −1'dir. İkincisi, eşitlik durumunda metot dönmez. Eşleşmenin indisini sonuc'a kaydeder ve son = orta − 1 ile solda daha önce bir eşleşme olup olmadığına bakar. Döngü, aralık boşalana kadar sürer ve sonunda sonuc döner. Orta hesabı da taşmaya karşı güvenli biçimde yazılmıştır.

Dizide dört tane 4 vardır (1–4 indisleri). Birinci turda 3. indisteki 4 bulunur, ama bu ilk 4 olmayabilir. Kaydedilir ve sola bakılır. İkinci turda 1. indisteki 4 bulunur; o da kaydedilir. Üçüncü turda 0. indisteki 2, aranandan küçüktür ve aralık sağa kayar. Aralık boşalınca son kaydedilen değer, yani 1 döner. 3 yoklama yapılmıştır ve süre yine O(log n)'dir.

Aynı fikir son konumu bulmak için de kullanılır: eşitlikte sonuç kaydedilir ve bas = orta + 1 ile sağa devam edilir. İki metodun farkı, aranan değerin dizide kaç kez geçtiğini de verir. Örnekte son konum 4, ilk konum 1'dir; 4 değeri 4 − 1 + 1 = 4 kez geçer. Bu sayım, tekrar sayısı ne olursa olsun O(log n) sürer.

3.4Hash ile arama

Şimdiye kadarki yöntemler aranan değerin yerini karşılaştırarak bulur. Her karşılaştırma bir miktar bilgi verir ve aday konumları azaltır. Karşılaştırmaya dayalı her yöntem için bir alt sınır vardır: sıralı bir dizide bile en kötü durumda yaklaşık log₂ n karşılaştırmadan kaçınılamaz. Hash ile arama bu sınırı başka bir yoldan aşar. Yeri aramaz, hesaplar.

3.4.1Fikir: yeri hesaplamak

Hash ile arama, bir anahtarın kendi kilidine tam oturmasına benzer bir mantıkla çalışır. Veriler anahtarlardan ve onlara karşılık gelen değerlerden oluşur. Anahtar, bir hash fonksiyonu ile bir tablo indisine dönüştürülür. Bu indise anahtarın hash değeri denir ve verinin tablodaki yerini gösterir.

Arama, anahtarın hash değerine karşılık gelen kovada yapılır. Kova boş değilse anahtar, kovadaki anahtarlarla karşılaştırılır. Eşleşme bulunursa arama biter. Aramanın maliyeti, hash değerinin hesaplanması ve o kovadaki birkaç karşılaştırmadan ibarettir. Bu maliyet tablodaki anahtar sayısından bağımsızdır. Bu yüzden iyi tasarlanmış bir hash tablosunda ortalama arama süresi O(1)'dir.

Bu notun örneklerinde anahtarlar tam sayıdır ve hash fonksiyonu h(x) = x % 10'dur. Bu fonksiyon anahtarın son basamağını alır ve onu kova numarası yapar. Fonksiyon basittir, ama ilkeyi göstermeye yeter. Gerçek uygulamalarda kova sayısı çoğu zaman bir asal sayı ya da ikinin kuvveti seçilir ve fonksiyon anahtarın bütün bitlerini kullanır.

3.4.2Avantajlar ve dezavantajlar

Hash ile aramanın avantajları şunlardır:

• Ortalama durumda çok hızlıdır: O(1).
• Verilerin önceden sıralanmasına gerek yoktur.
• Büyük veri kümelerinde ve çok sayıda ekleme ile aramanın karışık yapıldığı uygulamalarda idealdir. Sıralı dizide yeni bir öğe eklemek öğeleri kaydırmayı gerektirir; hash tablosunda ekleme de ortalama O(1)'dir.
• Hash fonksiyonu iyi seçilmişse aranan öğeye doğrudan erişilir.

Dezavantajları da vardır:

• Hash fonksiyonu çakışmalara yol açabilir.
• Çakışma olduğunda ek işlem adımları gerekir. En kötü durumda bütün anahtarlar aynı kovaya düşer ve arama O(n)'e çıkar.
• Ek bellek ister; tablonun bir kısmı her zaman boş tutulur.
• Tablo, anahtarları sıra gözetmeden dağıtır. Bu yüzden anahtarları sıralı gezmek, en küçük anahtarı bulmak ya da “50 ile 100 arasındaki anahtarlar” gibi aralık sorgularını yanıtlamak verimli değildir.

Çakışmalar kaçınılmazdır. Olası anahtarların sayısı kova sayısından çok büyüktür; güvercin yuvası ilkesine göre bazı anahtarlar aynı kovayı paylaşmak zorundadır. Örneğin bütün tam sayılar 10 kovaya dağıtılıyorsa son basamağı aynı olan her sayı aynı kovaya düşer. Bu yüzden hash tablosunun tasarımında iki soru vardır: çakışmaları azaltan bir hash fonksiyonu nasıl seçilir ve kaçınılmaz çakışmalar nasıl çözülür?

3.4.3Hash fonksiyonu

Anahtar bir dizge olduğunda önce onu bir sayıya çevirmek gerekir. En basit yol, karakterlerin sayısal kodlarını toplamaktır:

int hashFonksiyonu(String anahtar,
                   int m) {
  int toplam = 0;
  for (char k : anahtar.toCharArray())
    toplam += k;        // Unicode kodu
  return toplam % m;    // m: tablo boyu
}

Metot, anahtarın karakterlerini tek tek dolaşır. Java'da char türü bir tam sayı gibi davranır; toplam += k satırı karakterin Unicode kodunu toplama ekler. Döngü bitince toplam, tablo boyu m'ye göre mod alınarak 0 ile m − 1 arasına indirilir. Metot O(L) sürede çalışır; burada L anahtarın uzunluğudur.

Fonksiyon basittir ama zayıftır. Toplama işlemi sırayı görmez: harfleri aynı olan kelimeler her zaman aynı toplamı verir. “ali” ile “ila” bu yüzden 0 numaralı kovada çakışır. “kar” ile “ark” da aynı nedenle çakışır. Ayrıca kısa kelimelerin toplamları dar bir aralıkta toplanır; büyük bir tabloda kovaların çoğu hiç kullanılmaz.

İyi bir hash fonksiyonu iki özelliği birlikte taşır: hızlı hesaplanır ve anahtarları kovalara düzgün dağıtır. Java'nın String.hashCode() metodu her karaktere konumuna bağlı bir ağırlık verir:

h(s) = Σ_i=0^L−1 s[i] · 31^L−1−i

Bu toplamda karakterin yeri de önemlidir. “ali” için değer 97 · 31² + 108 · 31 + 105 = 96.670, “ila” için 104.350'dir; iki kelime artık ayrışır. Toplam büyük olabileceği için int taşar, ama bu bir sorun değildir: taşma değerleri karıştırmaya devam eder. Kova numarası, bu değerin işareti düzeltildikten sonra m'ye göre modu alınarak bulunur.

3.4.4Kod izleme: hashFonksiyonu("veli", 10)

3.4.5Doğrusal yoklama ile arama

Çakışmayı çözmenin iki ana yolu vardır. Birincisinde her anahtar tablonun kendi hücrelerinden birine yerleşir; kovası doluysa başka bir boş kova aranır. Bu yaklaşıma açık adresleme (open addressing) denir. En basit açık adresleme yöntemi doğrusal yoklamadır.

Doğrusal yoklama kullanan bir tabloda arama şöyle yazılır:

int hashArama(Integer[] tablo, int anahtar) {
  int m = tablo.length;
  int indis = anahtar % m;   // hash
  while (tablo[indis] != null) {
    if (tablo[indis] == anahtar)
      return indis;          // bulundu
    indis = (indis + 1) % m; // sonraki kova
  }
  return -1;                 // boş kova: yok
}

Tablo Integer[] türündedir, böylece boş kova null ile gösterilebilir. Bu örnekte tablo yalnız anahtarları saklar; genel bir uygulamada her kova bir anahtar-değer çifti tutar. m tablo boyudur. İlk bakılacak kova anahtar % m'dir.

while döngüsü, tablo[indis] boş olana kadar sürer. Her turda kovadaki anahtar aranan anahtarla karşılaştırılır. Eşleşirse kovanın indisi döner; anahtar-değer tablosunda burada değer döndürülürdü. Eşleşme yoksa bir sonraki kovaya geçilir. (indis + 1) % m ifadesi, son kovadan sonra 0 numaralı kovaya dönmeyi sağlar; tablo döngüsel olarak taranır. Boş bir kovaya varılırsa anahtar tabloda yoktur ve metot −1 döndürür.

Boş kovada durmanın mantığı eklemenin nasıl yapıldığından gelir. Bir anahtar eklenirken kendi kovasından başlayarak ilk boş kovaya yerleşir. Dolayısıyla anahtar tablodaysa, kendi kovasından onun yerine kadar olan bütün kovalar doludur. Arama sırasında bir boş kovaya rastlanırsa, anahtar daha ileride olamaz.

3.4.6Doğrusal yoklama ile ekleme

Boş bir tabloya (m = 10) şu anahtarlar sırayla eklensin: 16, 12, 45, 29, 6, 122, 5, 58, 75. Hash fonksiyonu h(x) = x % 10'dur.

İlk dört anahtar kendi kovalarına doğrudan yerleşir. 6'nın kovası 6'da 16 durduğu için bir sonraki kova olan 7'ye geçer. 122 de aynı biçimde 2'den 3'e kayar. 5'in durumu daha ilginçtir: 5, 6 ve 7 kovaları doludur, 5 ancak 8'e yerleşebilir. 58'in kendi kovası 8'i az önce 5 almıştır; 58, 9'u da dolu bulur ve tablonun sonundan başa dönerek 0'a yerleşir. Son anahtar 75'in kovası 5'tir ve 5'ten 0'a kadar bütün kovalar doludur. 75, yedi yoklamadan sonra 1 numaralı kovaya yerleşir.

Son durumda dolu kovalar 5, 6, 7, 8, 9, 0, 1, 2, 3 sırasıyla bitişik bir küme oluşturmuştur; yalnız 4 numaralı kova boştur. Bu olguya birincil kümelenme (primary clustering) denir. Küme büyüdükçe, kümenin herhangi bir kovasına düşen yeni anahtar kümenin sonuna kadar yürümek zorunda kalır ve kümeyi bir kova daha büyütür. Büyük kümeler daha büyük olma eğilimindedir. Doğrusal yoklamanın tablo dolarken hızla yavaşlamasının nedeni budur.

3.4.7Kod izleme: hashArama(tablo, 75)

Oluşan tabloda 75 aranıyor. Tablo [58, 75, 12, 122, null, 45, 16, 6, 5, 29] durumundadır.

Arama 75 % 10 = 5 numaralı kovadan başlar. 45, 16, 6, 5 ve 29 sırayla aşılır; 9 numaralı kovadan sonra sondan başa dönülür. 0 numaralı kovadaki 58 de aşılınca 1 numaralı kovada 75 bulunur ve metot 1 döndürür. Arama, eklemede olduğu gibi 7 yoklama sürmüştür: 75'in yerine kümenin sonunda ulaşılmıştır.

Başarısız bir arama daha pahalıdır. Aynı tabloda 35 aranırsa arama yine 5'ten başlar ve tek boş kova olan 4'e ulaşana kadar sürer: 5, 6, 7, 8, 9, 0, 1, 2, 3, 4 kovalarına bakılır. Dokuz anahtar karşılaştırması ve bir boş kova, toplam 10 yoklama yapılır. Bu tabloda başarılı aramaların ortalaması ise 22/9 ≈ 2,44 yoklamadır; çoğu anahtar kendi kovasına yakın durur.

3.4.8Zincirleme

Çakışma çözümünün ikinci yolu, bir kovaya birden çok anahtar koymaktır.

Aynı anahtarlar, aynı hash fonksiyonuyla zincirleme kullanan bir tabloya eklensin. 16, 12, 45 ve 29 boş kovalara düşer ve birer öğeli listeler oluşur. 6 eklenirken 6 numaralı kova doludur; bu bir çakışmadır, ama 6 başka bir kovaya kaymaz, 16'nın listesinin sonuna eklenir. 122, 2 numaralı kovanın listesine 12'den sonra eklenir. 5, kova 5'in listesinde 45'in arkasına geçer. 58 boş olan 8 numaralı kovaya yerleşir. Son olarak 75, kova 5'in listesine üçüncü öğe olarak eklenir.

Zincirlemede 75'i aramak için yalnız kova 5'in listesi gezilir: 45 ≠ 75, 5 ≠ 75, 75 = 75. Üç karşılaştırmada bulunur. Doğrusal yoklamadaki 7 yoklamaya göre bu çok daha azdır, çünkü zincirlemede kümelenme olmaz. Her anahtar yalnız kendi kovasıyla aynı hash değerini taşıyan anahtarlarla karşılaştırılır. Kova 6'ya düşen 16 ile kova 5'e düşen 75 hiçbir zaman karşılaşmaz.

Zincirlemenin başka üstünlükleri de vardır. Tablo hiçbir zaman “dolmaz”; listeler uzayabilir. Silme de kolaydır: öğe listeden çıkarılır. Doğrusal yoklamada ise bir anahtarı silip kovayı boşaltmak, arkasındaki anahtarlara giden yolu keser; silinen kovaya “silindi” işareti koymak gerekir. Zincirlemenin bedeli, her düğüm için ayrı bir nesne ve bir işaretçi saklamaktır. Bu, hem ek bellek hem de bellekte dağınık erişim demektir. Doğrusal yoklama ise anahtarları ardışık hücrelerde tuttuğu için önbelleği daha iyi kullanır.

3.4.9Yük faktörü ve karmaşıklık

Hash tablosunun başarımını belirleyen asıl büyüklük, tablonun ne kadar dolu olduğudur.

Zincirlemede α, bir listenin ortalama uzunluğudur ve 1'i aşabilir. Doğrusal yoklamada her kova en fazla bir anahtar tuttuğu için α ≤ 1'dir. Örnek tablolarımızda 10 kovaya 9 anahtar konmuştur: α = 0,9.

Knuth, anahtarların kovalara rastgele ve birbirinden bağımsız dağıldığı düzgün hash varsayımı altında ortalama yoklama sayıları için şu yaklaşık formülleri verir:

Tablodaki sayılar formüllerden doğrudan hesaplanır. Örneğin doğrusal yoklamada α = 0,9 için başarısız arama ½ (1 + 1/0,1²) = ½ (1 + 100) = 50,5 yoklama ister. Zincirlemede maliyet α ile doğrusal olarak artar. Doğrusal yoklamada ise 1/(1 − α)² terimi α 1'e yaklaşırken sınırsız büyür. Tablo yarı doluyken iki yöntem arasındaki fark küçüktür; yüzde doksan doluyken doğrusal yoklamada başarısız arama zincirlemeden yaklaşık 27 kat pahalıdır.

Formüller ortalama değerlerdir ve gerçek bir tablo bunlardan sapabilir. Örnek doğrusal yoklama tablomuzda α = 0,9 iken başarılı aramaların ortalaması 2,44 yoklamaydı; formül 5,5 verir. Fark, dokuz anahtarlık küçük örnekte anahtarların çoğunun kendi kovasına yakın yerleşmiş olmasından gelir. Zincirleme tablosunda ise başarılı aramaların ortalaması 14/9 ≈ 1,56'dır ve formülün verdiği 1,45'e yakındır.

Yük faktörünü sabit tutmanın yolu, tablo belli bir doluluğa ulaştığında onu büyütmektir. Yaygın uygulama şudur: α, 0,75 gibi bir eşiği aşınca iki kat büyüklükte yeni bir tablo ayrılır ve bütün anahtarlar yeni tabloya yeniden yerleştirilir. Hash değerleri kova sayısına bağlı olduğu için anahtarlar kopyalanmaz, yeniden hash'lenir. Bu işlem O(n) sürer, ama seyrek yapılır; dinamik dizinin iki katına büyütülmesinde olduğu gibi ekleme başına amortize maliyeti sabittir. Java'nın HashMap sınıfı varsayılan olarak 0,75 eşiğini kullanır.

En kötü durum ise O(n)'dir. Kötü bir hash fonksiyonu bütün anahtarları aynı kovaya düşürebilir. Bu durumda arama tek bir uzun listeyi ya da kümeyi tarar; yani doğrusal aramaya dönüşür. h(x) = x % 10 fonksiyonuyla 10, 20, 30, … gibi anahtarların hepsi 0 numaralı kovaya düşer. Doğrusal yoklamada α 1'e yaklaşırken kümelenme maliyeti hızla büyütür. Tablo tamamen dolarsa ve aranan anahtar tabloda yoksa boş kova hiç bulunamaz; hashArama'nın döngüsü hiç bitmez.

3.5Ara değer arama

İkili arama, aranan değer ne olursa olsun aralığın tam ortasına bakar. İnsanlar böyle aramaz. Telefon rehberinde “Yılmaz” aranırken rehber ortadan değil, sona yakın bir yerden açılır; “Akın” aranırken başa yakın bir yerden. Ara değer arama bu davranışı bir formüle döker.

3.5.1Fikir: konumu tahmin etmek

Ara değer arama (interpolation search) sıralı veri kümelerinde kullanılır. Değerlerin aralık boyunca eşit aralıklarla dağıldığını varsayar: ardışık öğeler arasındaki fark yaklaşık aynıdır. Bu varsayım altında indis ile değer arasındaki ilişki bir doğruya yakındır. Aranan değerin konumu, aralığın en küçük ve en büyük öğesinden geçen doğru üzerinde tahmin edilir. Tahmin edilen konum yoklanır. Değer eşleşmezse arama, tıpkı ikili aramadaki gibi, tahminin solunda ya da sağındaki daha dar aralıkta sürer.

Tahmin formülü doğru denkleminden çıkar. Aralığın uçları (bas, dizi[bas]) ve (son, dizi[son]) noktalarıdır. Bu iki noktadan geçen doğru üzerinde değeri aranan olan noktanın indisi şöyledir:

Formülün yapısı sezgiyle okunabilir. (aranan − dizi[bas]) / (dizi[son] − dizi[bas]) oranı, aranan değerin değer aralığında ne kadar ilerde olduğunu gösterir; 0 ile 1 arasında bir sayıdır. Bu oran indis aralığının uzunluğu son − bas ile çarpılıp bas'a eklenince tahmini konum elde edilir. Aranan değer en küçük değere eşitse oran 0'dır ve bas yoklanır; en büyük değere eşitse oran 1'dir ve son yoklanır. İkili arama bu oranı her zaman ½ alan özel bir durum gibi düşünülebilir.

3.5.2Kod: araDegerArama()

int araDegerArama(int[] dizi, int n,
                  int aranan) {
  int bas = 0, son = n - 1;
  while (bas <= son && aranan >= dizi[bas]
                    && aranan <= dizi[son]) {
    if (dizi[son] == dizi[bas]) return bas; // 0'a bölme
    int pay = (aranan - dizi[bas]) * (son - bas);
    int indis = bas + pay / (dizi[son] - dizi[bas]);
    if (dizi[indis] == aranan) return indis;
    if (dizi[indis] < aranan) bas = indis + 1;
    else son = indis - 1;
  }
  return -1;
}

bas ve son yine arama aralığının sınırlarıdır. Döngü koşulu ikili aramadakinden zengindir: aralık boş olmamalı (bas <= son) ve aranan değer aralığın uç değerleri arasında kalmalıdır (aranan >= dizi[bas] ve aranan <= dizi[son]). Aranan değer uçların dışındaysa aralıkta olamaz; döngüye girilmez ve −1 döner. Bu denetim aynı zamanda tahmini indisin aralık içinde kalmasını güvenceye alır. Aranan uçların dışında olsaydı oran 0'dan küçük ya da 1'den büyük çıkar ve indis dizinin dışına taşabilirdi.

Döngünün ilk satırı sıfıra bölmeyi önler. dizi[son] == dizi[bas] ise aralıktaki bütün değerler eşittir. Döngü koşulu sağlandığına göre aranan da bu değere eşittir ve bas döndürülebilir. Ardından pay ve indis hesaplanır. Pay ile paydanın ayrı yazılması, işlem sırasını açıkça belirler: önce çarpma, sonra bölme. Önce bölme yapılsaydı tam sayı bölmesi oranı çoğu zaman 0'a yuvarlardı. Son olarak tahmini indisteki değer yoklanır. Eşitse indis döner. Küçükse aranan sağdadır, bas = indis + 1. Büyükse aranan soldadır, son = indis − 1. Aralık boşalırsa ya da aranan uçların dışına düşerse döngü biter ve −1 döner.

3.5.3Kod izleme: araDegerArama(dizi, 15, 24)

Dağılımı yaklaşık düzgün, ama tam düzgün olmayan bir dizi şudur:

dizi = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47}, n = 15

Aranan 24'tür. Dizinin ilk on bir öğesi sık, son dört öğesi seyrek dağılmıştır.

İlk tahmin 196/37 ≈ 5,3'tür ve aşağı yuvarlanarak 5 olur. dizi[5] = 19 aranandan küçüktür; arama 6. indisten devam eder. Her yoklamada aralığın sol ucu yükselir, ama sağ uç hep 47'de kalır. 47 dizinin geri kalanından belirgin biçimde büyük olduğu için tahminleri sola çeker: ikinci yoklamada oran 4/27, üçüncüde 2/25'tir. Arama hedefe adım adım yaklaşır ve beşinci yoklamada 10. indiste 24'ü bulur.

Bu dizide ikili arama 24'ü 7, 11, 9, 10 indislerini yoklayarak dört adımda bulurdu. Ara değer arama burada ikili aramadan yavaştır. Dizinin dağılımı “yaklaşık düzgün” olsa da sondaki seyrek değerler tahmini bozmuştur. Ara değer aramanın hızı tamamen dağılımın düzgünlüğüne bağlıdır.

3.5.4Karmaşıklık ve kötü durum

Düzgün ve rastgele dağılmış anahtarlarda ortalama yoklama sayısı O(log log n)'dir. Bu sonucu Perl, Itai ve Avni 1978'de kanıtlamıştır. Kanıt bu notun kapsamı dışındadır, ama sezgisi şöyle anlatılabilir. Düzgün dağılımda her tahminin hatası, kalan aralık boyunun karekökü mertebesindedir. Yani aralık her yoklamada yaklaşık n'den √n'ye iner: n → n^1/2 → n^1/4 → …. Aralığın sabit boya inmesi için gereken adım sayısı log log n mertebesindedir. İkili arama logaritmayı bir kez alır; ara değer arama iki kez.

Sayılarla bakınca fark çarpıcıdır. n = 10⁶ için log₂ log₂ n ≈ log₂ 19,93 ≈ 4,3'tür; ikili arama ise yaklaşık 20 yoklama yapar. Ancak bu kazancın iki bedeli vardır:

• Her yoklama ikili aramadakinden pahalıdır: bir çıkarma ve bölme yerine çarpma, bölme ve birkaç çıkarma içerir. Bellekten okuma yavaşsa, örneğin veri diskteyse, yoklama sayısını azaltmak bu bedele değer. Veri bellekteyse kazanç çoğu zaman küçüktür.
• Ara çarpım (aranan − dizi[bas]) · (son − bas) büyük değerlerde int'i taşırabilir. Değerler 10⁹, son − bas ise 10⁶ mertebesindeyse çarpım 10¹⁵ olur ve 2³¹ − 1 sınırını çok aşar. Bu durumda çarpım long ile yapılmalıdır.

Kötü durumun kaynağı, formülün uç değerlere güvenmesidir. Tek bir aykırı değer, aralığın geri kalanındaki bütün tahminleri bozar. Üstel büyüyen bir dizide, örneğin 2, 4, 8, …, 256 dizisinde 32 aranırken de aynı durum görülür: tahminler 0, 1, 2, 3, 4 diye birer birer ilerler. En kötü durum O(n)'dir. Bu yüzden ara değer arama, dağılımı bilinen ve düzgün olan sayısal anahtarlarda kullanılır. Sıralı kimlik numaraları ya da düzenli aralıklarla alınmış zaman damgaları iyi örneklerdir. Pratikte ara değer adımlarını ikili arama adımlarıyla karıştıran melez yöntemler de kullanılır; böylece en kötü durum O(log n)'de tutulur.

3.6Atlayarak arama

İkili arama dizinin içinde büyük sıçramalar yapar: ortadan bir çeyreğe, oradan bir sekizde bire. Veri bellekteyse bu sıçramaların bedeli yoktur. Ama bazı ortamlarda geriye gitmek ya da uzak bir konuma atlamak pahalıdır. Atlayarak arama bu ortamlar için tasarlanmıştır.

3.6.1Fikir: bloklar hâlinde ilerlemek

Atlayarak arama (jump search), engelli koşuda engelleri aşarak ilerleyen bir atlet gibi çalışır; dizi sıralı olmalıdır. Liste m büyüklüğünde bloklara ayrılır ve blok boyu genellikle m = √n seçilir. Listenin başından büyük bir adım atılır ve o konumdaki öğe, yani bloğun son öğesi kontrol edilir. Bu öğe aranandan küçükse aranan bu blokta olamaz; bir sonraki bloğa atlanır. Bloğun son öğesi aranandan büyük ya da ona eşitse aranan, varsa, bu bloktadır. Arama o bloğun başına döner ve blok içinde doğrusal arama yapar.

Geri dönüş, ikili aramadaki gibi büyük sıçramalar gerektirmez. Veri hep ileri yönde okunur; yalnız son blokta bir kez, en fazla m adım geri gidilir. Bu yüzden atlayarak arama geriye gitmenin pahalı olduğu ortamlarda tercih edilir. Manyetik bant ileri yönde hızlı okunur, geri sarma yavaştır. Disk üzerindeki büyük bir dosya bloklar hâlinde okunur; her blok okuması pahalıdır ve atlanan bloklar hiç okunmaz.

3.6.2Kod: atlayarakAraBul()

int atlayarakAraBul(int[] dizi, int eleman,
                    int n) {
  int blok = (int) Math.sqrt(n);
  int atlama = blok, konum = 0;
  while (dizi[Math.min(atlama, n) - 1] < eleman) {
    konum = atlama; atlama += blok; // atla
    if (konum >= n) return -1;
  }
  while (dizi[konum] < eleman) {     // doğrusal
    konum++;
    if (konum == Math.min(atlama, n)) return -1;
  }
  if (dizi[konum] == eleman) return konum;
  return -1;
}

Atlama mesafesi Math.sqrt(n) ile hesaplanır ve tam sayıya çevrilir; blok, ⌊√n⌋'dir. konum o anki bloğun başını, atlama ise bir sonraki bloğun başını gösterir. Bloğun son öğesi dizi[atlama − 1]'dir.

İlk döngü blokları atlar. Her turda bloğun son öğesine bakılır. Math.min(atlama, n) ifadesi, son bloğun tam dolu olmadığı durumda dizinin dışına çıkmayı önler; bu durumda dizinin son öğesine bakılır. Bloğun son öğesi aranandan küçükse aranan bu blokta değildir: konum bir sonraki bloğun başına, atlama da bir blok ileriye taşınır. konum dizinin sonunu geçmişse aranan, dizinin bütün öğelerinden büyüktür ve −1 döner.

İlk döngü bittiğinde aranan, varsa, [konum, atlama) aralığındadır. İkinci döngü bu aralığı doğrusal tarar. Taranan öğe aranandan küçük oldukça konum bir artar. Bloğun sonuna gelinmişse aranan bu blokta yoktur ve −1 döner. Döngü, aranandan küçük olmayan bir öğede durur. Son satırdaki denetim bu öğenin aranana eşit olup olmadığına bakar: eşitse indis, değilse −1 döner.

3.6.3Kod izleme: atlayarakAraBul(dizi, 69, 10)

Dizi on öğelidir: {2, 9, 30, 32, 38, 47, 61, 69, 79, 81}. Aranan 69'dur.

Başarısız bir arama da benzer yürür. Aynı dizide 50 aranırsa 2, 5 ve 8 indislerine bakılır; 79 ≥ 50 olduğu için [6, 9) bloğuna geçilir. dizi[6] = 61 zaten 50'den büyüktür; doğrusal döngü hiç dönmez. Son denetimde 61 ≠ 50 olduğu için −1 döner. Yoklanan indisler 2, 5, 8, 6'dır.

3.6.4Neden √n?

Blok boyu m iken en kötü durumdaki yoklama sayısı şöyle bulunur. Atlama aşamasında en fazla n/m blok sonuna bakılır. Doğrusal aşamada bloğun içinde en fazla m − 1 öğe taranır; bloğun son öğesine zaten bakılmıştı. Toplam:

f(m) = n/m + (m − 1)

İki terim zıt yönde davranır. Bloklar küçükse atlama sayısı artar; m = 1 için arama doğrusal aramaya döner. Bloklar büyükse blok içi tarama uzar; m = n için yine doğrusal aramaya dönülür. En iyi değer arada bir yerdedir.

Aynı sonuç türev kullanmadan da görülebilir. İki pozitif sayının çarpımı sabitse toplamları, sayılar eşit olduğunda en küçüktür. n/m ile m'nin çarpımı her zaman n'dir; bu yüzden toplam n/m = m olduğunda, yani m = √n iken en küçüktür.

Karmaşıklık O(√n)'dir: doğrusal aramanın O(n)'i ile ikili aramanın O(log n)'i arasında kalır. Ek bellek O(1)'dir. Blok boyunun yanlış seçilmesi maliyeti hissedilir biçimde artırır. n = 10.000 için m = 50 seçilirse en kötü durum 200 + 49 = 249 yoklama olur; en iyi seçim olan m = 100 ile 199'dur.

Blok bulunduktan sonra blok iki yönde taranabilir. Kod, bloğun başından ileri doğru tarar (69 aramasında 6 → 7). Bloğun sonundan geriye doğru da taranabilirdi (8 → 7). İki yol da en fazla m − 1 ek yoklama yapar. Bir iyileştirme daha mümkündür: blok bulunduktan sonra içeride doğrusal arama yerine yine atlayarak (√m adımla) ya da ikili arama yapılabilir. Ancak ikili arama kullanılabilecekse atlayarak arama başından gereksizdir. Atlayarak arama yalnız geri gitmenin pahalı olduğu durumlarda anlamlıdır.

3.7Üstel arama

İkili arama dizinin boyunu bilmek zorundadır; ilk adımda son = n − 1 atanır. Bazı durumlarda boy bilinmez ya da çok büyüktür. Örneğin sıralı bir veri akışı sürekli uzar ya da çok büyük bir dosyanın sonuna gitmek pahalıdır. Üstel arama önce aranan değeri içeren bir aralık bulur, sonra o aralıkta ikili arama yapar.

3.7.1Fikir: sınırı katlamak

Üstel arama (exponential search) sıralı listeyi üstel olarak büyüyen parçalara ayırır. Sınır, yani konum, 1, 2, 4, 8, 16, … diye her adımda ikiye katlanır. dizi[konum] aranandan büyük olunca durulur. Bu anda aranan, varsa, [konum/2, konum] aralığındadır, çünkü bir önceki sınır olan konum/2'deki değer aranandan büyük değildi. Bu aralıkta ikili arama yapılır. Yöntem, Bentley ve Yao'nun 1976'da sınırsız diziler için önerdiği aramaya dayanır.

Yöntemin üstünlüğü, maliyetin n'ye değil aranan öğenin konumu i'ye bağlı olmasıdır. Dizinin boyu bilinmiyorsa (sınırsız ya da akan veri) ya da aranan öğe başa yakınsa üstel arama idealdir. Aranan 10. indisteyse dizinin bir milyon ya da bir milyar öğeli olması fark etmez; arama birkaç adımda biter.

3.7.2Kod: ustelArama()

int ustelArama(int[] dizi, int aranan, int n) {
  if (dizi[0] == aranan) return 0;
  int konum = 1;
  while (konum < n && dizi[konum] <= aranan)
    konum *= 2;               // 1, 2, 4, 8, ...
  int bas = konum / 2, son = Math.min(konum, n - 1);
  while (bas <= son) {        // ikili arama
    int orta = (bas + son) / 2;
    if (dizi[orta] == aranan) return orta;
    if (dizi[orta] < aranan) bas = orta + 1;
    else son = orta - 1;
  }
  return -1;
}

Metot önce 0. indisi ayrıca denetler, çünkü katlama 1'den başlar ve 0. indis katlamada hiç yoklanmaz. Ardından konum = 1 alınır. dizi[konum] <= aranan olduğu sürece konum 2 ile çarpılır. konum < n koşulu dizinin dışına çıkmayı önler. Döngü sonunda konum, aranan değerin olabileceği aralığın sonunu gösterir; konum / 2 ise başını. Son katlamada konum dizinin dışına çıkmış olabileceği için üst sınır Math.min(konum, n − 1) ile alınır. Kalan kısım, yinelemeli ikili aramanın aynısıyla taranır.

Son aşamada ikili arama yerine konum / 2'den sona doğru doğrusal tarama yapılsaydı maliyet O(i) olurdu; aranan dizide yoksa dizinin sonuna kadar gidilirdi. Aralığın boyu i ile orantılıdır ve onu ikili aramayla taramak maliyeti O(log i)'ye indirir.

3.7.3Kod izleme: ustelArama(dizi, 47, 10)

Dizi, atlayarak arama örneğindeki dizidir: {2, 9, 30, 32, 38, 47, 61, 69, 79, 81}. Aranan 47'dir.

Toplam 8 yoklama yapılmıştır: 0, 1, 2, 4, 8, 6, 4, 5. 4. indise iki kez bakılmıştır. Katlama aşamasında 38 ≤ 47 sınaması yapılmış, ikili arama da aralığın alt ucu olan 4'ü yeniden yoklamıştır. Katlama aşaması 4. indisteki değerin aranandan büyük olmadığını zaten göstermişti; ikili arama bas = konum / 2 + 1 ile başlatılsaydı bu tekrar önlenirdi. Bu dizide ikili arama 47'yi 3 yoklamada bulur: aranan dizinin başında değilse üstel arama ikili aramadan yavaştır.

3.7.4Karmaşıklık

Üstel arama, aranan başa yakınsa ikili aramadan hızlıdır; sona yakınsa yaklaşık iki kat yavaştır. Tablo 3.16, bir milyon öğeli bir dizide farklı konumlar için iki yöntemi karşılaştırır.

Kırılma noktası i ≈ √n civarındadır: 2 log₂ i = log₂ n eşitliği i = √n verir. Bir milyon öğede bu nokta 1000'dir ve tablo da bunu gösterir.

Üstel aramanın başlıca kullanım alanları şunlardır: boyu bilinmeyen sıralı listeler, büyük bir dosyada başa yakın kayıtlar ve sıralı veri akışları. Aynı fikrin bir uygulaması “dörtnala” (galloping) aramadır. Timsort sıralama algoritması iki sıralı diziyi birleştirirken bazen bir dizinin uzun bir parçası ötekinin önüne geçer. Timsort bu parçanın sonunu tek tek değil, dörtnala aramayla bulur.

3.8Karşılaştırma ve seçim

Yedi yöntemin her biri belli bir durumda en iyisidir. Doğru seçim için önce yöntemlerin maliyetlerini yan yana koymak, sonra aynı veri üzerinde nasıl davrandıklarını görmek gerekir.

3.8.1Karşılaştırma tablosu

Tabloyu okurken üç noktayı akılda tutmak gerekir. Birincisi, hash tablosunun ortalama O(1)'i yük faktörünün sabit tutulmasına bağlıdır; tablo dolmaya bırakılırsa bu güvence kaybolur. İkincisi, sıralı dizi isteyen yöntemlerde dizi baştan sıralı değilse bir kez O(n log n) sıralama maliyeti eklenir. Üçüncüsü, en kötü durum sütunu algoritmanın verdiği güvencedir. Hash tablosu ve ara değer arama ortalamada çok hızlıdır, ama kötü bir girdiye karşı hiçbir güvence vermez. İkili arama ise her girdide O(log n)'dir. Bu öngörülebilirlik, onu çoğu durumda varsayılan seçim yapar.

3.8.2Aynı dizide yoklama sayıları

Mertebeler büyük n için konuşur. Küçük bir dizide yöntemlerin gerçekte kaç yoklama yaptığını görmek de öğreticidir. Atlayarak ve üstel arama örneklerindeki on öğeli dizi kullanılıyor:

dizi = {2, 9, 30, 32, 38, 47, 61, 69, 79, 81}

Tablodan birkaç ders çıkar. Dizi neredeyse düzgün dağıldığı için ara değer arama her sorguyu tek yoklamada sonuçlandırır. 69 için tahmin 0 + (69 − 2) · 9 / 79 = 603/79 ≈ 7,6 → 7'dir ve doğrudan hedefe düşer. 50 aranırken ara değer arama 5. indisteki 47'yi yoklar. Ardından bas = 6 olur ve aranan, yeni aralığın alt ucu olan 61'den küçük kaldığı için döngü hemen biter; sonuç −1'dir.

İkili arama her sorguda en fazla 4 yoklama yapar; bu, ⌊log₂ 10⌋ + 1 = 4 sınırıdır. Atlayarak arama bloğa göre değişir. 47 aranırken ikinci bloğun son öğesi tam olarak 47'dir, ama kod blok sonunda durmaz; bloğun başına dönüp 3, 4, 5 indislerini tarar. Üstel arama ise aranan değer dizinin başında olduğunda parlar: 2 için tek yoklama yeter. Aranan sona yaklaştıkça katlama ve ikili arama aşamaları birlikte ikili aramadan pahalı olur. 47 ve 50 aramalarında 4. indis iki kez yoklanır: bir kez katlamada, bir kez ikili aramada.

Bu kadar küçük bir dizide farklar birkaç yoklamadır. Dizi büyüdükçe mertebe farkları belirleyici olur. Bir milyon öğede doğrusal arama ortalama yarım milyon, atlayarak arama en fazla yaklaşık iki bin, ikili arama en fazla 20 yoklama yapar.

3.8.3Hangi algoritma ne zaman?

Seçim, verinin özelliklerine ve sorguların biçimine bağlıdır:

• Doğrusal arama: sırasız ya da küçük veri, bağlı liste, tek seferlik arama.
• İkili arama: sıralı dizi ve çok sayıda sorgu; genel amaçlı varsayılan seçim.
• Hash tablosu: yalnız tam eşleşme sorgusu ve çok sayıda ekleme ile arama; sıra gerekmiyor.
• Ara değer arama: sıralı ve düzgün dağılmış sayısal anahtarlar, örneğin sıralı kimlik numaraları.
• Atlayarak arama: geriye gitmenin pahalı olduğu sıralı ortamlar, örneğin bant ya da blok blok okunan disk.
• Üstel arama: boyu bilinmeyen sıralı liste ya da aranan değerin başa yakın olduğu durumlar.

Bu kurallar bir soru sırasına dönüştürülebilir. İlk soru, verinin sıralı olup olmadığıdır. Veri sırasızsa iki yol vardır: tek ya da birkaç arama yapılacaksa doğrusal arama, çok sayıda arama yapılacaksa bir hash tablosu kurmak. Veri sıralıysa varsayılan seçim ikili aramadır. Dağılım düzgünse ara değer arama, boy bilinmiyorsa üstel arama, geri gitmek pahalıysa atlayarak arama düşünülür.

3.9Sık yapılan hatalar

Arama algoritmaları kısa kodlardır, ama hata yapmaya çok elverişlidir. Hataların çoğu sınır koşullarında ortaya çıkar ve küçük örneklerle yapılan denemelerde gözden kaçar.

Bu hataların ortak bir dersi vardır: arama kodu yazıldıktan sonra sınır durumlarıyla denenmelidir. En az şu durumlar denenmelidir: boş dizi, tek öğeli dizi, aranan değerin ilk ya da son öğe olması, bütün değerlerden küçük ya da büyük olması ve iki öğe arasına düşmesi. İkili aramanın doğru yazımı zor olduğu için Java'da mümkün olduğunca Arrays.binarySearch ya da Collections.binarySearch kullanmak da iyi bir alışkanlıktır.

3.10Özet

• Arama problemi: bir dizide aranan değerin indisini bulmak; yoksa −1 döndürmek. Maliyet, yoklama (karşılaştırma) sayısıyla ölçülür.
• Doğrusal arama: baştan sona tek tek karşılaştırır; önkoşul yoktur. Başarılı aramada ortalama (n + 1)/2, en kötü durumda n karşılaştırma yapar: O(n). Sırasız veride daha iyisi yoktur.
• Bekçili doğrusal arama: aranan değeri son hücreye yazarak döngüdeki i < n sınamasını kaldırır; karşılaştırma sayısı yaklaşık 2n'den n + 2'ye iner, mertebe değişmez.
• İkili arama: sıralı dizide orta öğeyle karşılaştırır ve yarıyı eler. En fazla ⌊log₂ n⌋ + 1 karşılaştırma yapar: O(log n). Yinelemeli sürüm O(1), özyinelemeli sürüm O(log n) ek bellek kullanır. Sıralı dizi, örtük bir dengeli ikili arama ağacıdır.
• İkili aramada ayrıntılar: orta hesabı taşmaya karşı bas + (son − bas) / 2 ile yapılır; sınırlar ±1 ile güncellenir; ilk konum için eşitlikte sonuç kaydedilip sola devam edilir.
• Hash ile arama: yeri h(anahtar) ile hesaplar. Çakışmalar doğrusal yoklama ya da zincirleme ile çözülür. Yük faktörü α = n/m sabit tutulursa ortalama O(1); en kötü durum O(n). Doğrusal yoklamada birincil kümelenme α 1'e yaklaşırken maliyeti hızla büyütür.
• Ara değer arama: konumu uç değerlere göre orantıyla tahmin eder. Düzgün dağılımda O(log log n), çarpık dağılımda O(n)'dir.
• Atlayarak arama: √n'lik blokları atlar, sonra bloğun içinde doğrusal arar. En kötü durum yaklaşık 2√n − 1 yoklama, yani O(√n)'dir; geri gitmenin pahalı olduğu ortamlarda anlamlıdır.
• Üstel arama: sınırı 1, 2, 4, … diye katlar, sonra [konum/2, konum] aralığında ikili arama yapar. Maliyet aranan öğenin indisine bağlıdır: O(log i). Boyu bilinmeyen listelerde ve başa yakın aramalarda kullanılır.
• Seçim: veri sırasızsa doğrusal arama ya da hash tablosu; sıralıysa varsayılan ikili arama; düzgün dağılımda ara değer, bilinmeyen boyda üstel, pahalı geri dönüşte atlayarak arama.

3.11Kavram listesi

• arama problemi search problem
• yoklama probe
• en iyi durum best case
• ortalama durum average case
• en kötü durum worst case
• doğrusal arama linear search
• bekçi sentinel
• ikili arama binary search
• logaritmik logarithmic
• böl ve fethet divide and conquer
• azalt ve fethet decrease and conquer
• özyineleme bağıntısı recurrence relation
• hash tablosu hash table
• hash fonksiyonu hash function
• kova bucket
• çakışma collision
• açık adresleme open addressing
• doğrusal yoklama linear probing
• birincil kümelenme primary clustering
• zincirleme (separate) chaining
• yük faktörü load factor
• ara değer arama interpolation search
• atlayarak arama jump search
• üstel arama exponential search

3.12Kendini Dene

1. gozcuIleAra(dizi, 5, 9) çağrısı dizi = {12, 5, 9, 20, 7} için çalışıyor. Metot ne döndürür ve toplam kaç karşılaştırma yapılır?

   Cevap

   Son hücreye bekçi olarak 9 yazılır, sonEleman = 7. Döngü 12 ≠ 9 ve 5 ≠ 9'dan sonra 2. indisteki gerçek 9'da durur: 3 karşılaştırma. 7 geri konur. i < n − 1, yani 2 < 4 doğrudur; kısa devre || nedeniyle ikinci koşul hiç sınanmaz. Metot 2 döndürür; toplam 4 karşılaştırma yapılır.

2. {4, 9, 13, 20, 26, 31, 40, 48, 55, 61, 77} dizisinde yinelemeli ikili arama 50'yi arıyor. Hangi indisler yoklanır? Döngü bittiğinde bas ve son kaçtır ve bas neyi gösterir?

   Cevap

   Yoklanan indisler 5 (31 < 50, bas = 6), 8 (55 > 50, son = 7), 6 (40 < 50, bas = 7) ve 7'dir (48 < 50, bas = 8). Döngü bas = 8, son = 7 ile biter ve −1 döner. bas, 50'nin sırayı bozmadan ekleneceği konumdur: 48 ile 55 arasındaki 8. indis.

3. ilkKonum({1, 3, 3, 3, 3, 3, 8}, 3) çağrısında her turdaki orta ve sonuc değerleri nedir? Aynı dizide son 3'ün konumunu bulan sürüm hangi indisleri yoklar?

   Cevap

   Tur 1: orta = 3, eşit, sonuc = 3, son = 2. Tur 2: orta = 1, eşit, sonuc = 1, son = 0. Tur 3: orta = 0, 1 < 3, bas = 1. Döngü biter, 1 döner. Son konum sürümü eşitlikte bas = orta + 1 ile sağa gider: 3, 5, 6 indislerini yoklar ve 5 döndürür. 3 değeri 5 − 1 + 1 = 5 kez geçer.

4. m = 7, h(x) = x % 7 ve doğrusal yoklama kullanan boş bir tabloya 15, 22, 8, 29, 3 sırayla ekleniyor. Son tablo nedir? Ardından 36 aranırsa kaç kova yoklanır?

   Cevap

   15, 22, 8 ve 29'un dördü de 1 numaralı kovaya düşer: 15 → 1, 22 → 2, 8 → 3, 29 → 4 (yoklamalar 1, 2, 3, 4). 3'ün kovası 3'tür, ama 3 ve 4 doludur; 3, 5'e yerleşir. Tablo [—, 15, 22, 8, 29, 3, —] olur. 36 için h = 1: 1, 2, 3, 4, 5 kovalarındaki anahtarlar aşılır ve 6 numaralı boş kovada durulur. 6 yoklama yapılır, sonuç −1'dir.

5. Aynı beş anahtar m = 7 kovalı bir zincirleme tablosuna eklenirse yük faktörü kaçtır, hangi listeler oluşur? 36 aranırken kaç anahtar karşılaştırılır?

   Cevap

   α = 5/7 ≈ 0,71. Kova 1'in listesi 15 → 22 → 8 → 29, kova 3'ünki yalnız 3'tür; diğer kovalar boştur. 36 aranırken kova 1'in listesindeki 4 anahtar karşılaştırılır ve liste biter. Bu örnekte zincirleme de yavaştır: sorunun kaynağı hash fonksiyonunun anahtarları tek kovada toplamasıdır, çakışma çözüm yöntemi değil.

6. 5, 10, 15, …, 100 dizisinde (20 öğe) ara değer arama 65'i ve 63'ü kaç yoklamada sonuçlandırır? İkili arama 65 için hangi indisleri yoklar?

   Cevap

   65: indis = 0 + (65 − 5) · 19 / 95 = 1140/95 = 12, dizi[12] = 65; 1 yoklama. 63: 58 · 19 / 95 = 1102/95 ≈ 11,6 → 11, dizi[11] = 60 < 63, bas = 12. Artık 63 < dizi[12] = 65 olduğu için döngü biter: 1 yoklama, sonuç −1. İkili arama 65 için 9, 14, 11, 12 indislerini yoklar: 4 yoklama.

7. Atlayarak aramada n = 25 ve n = 400 için en iyi blok boyu ve en kötü durumdaki yoklama sayısı nedir? n = 400 için blok boyu yanlışlıkla 10 seçilirse ne olur?

   Cevap

   n = 25: m = 5, 25/5 + 4 = 9 yoklama. n = 400: m = 20, 20 + 19 = 39 yoklama. m = 10 seçilirse 400/10 + 9 = 49 yoklama olur; en iyi seçimden 10 fazla.

8. Bir milyon öğeli bir dizide dizi[i] = 2i'dir. Üstel arama 74'ü (indis 37) ararken hangi indisleri yoklar? İkili arama en fazla kaç yoklama yapardı?

   Cevap

   Önce 0. indis: 0 ≠ 74. Katlama 1, 2, 4, 8, 16, 32 indislerinde değer 74'ten küçük çıkar, 64. indiste 128 > 74 olur ve durulur. Aralık [32, 64]'tür. İkili arama 48, 39, 35, 37 indislerini yoklar ve 37'yi bulur. Toplam 12 yoklama: 0, 1, 2, 4, 8, 16, 32, 64, 48, 39, 35, 37. İkili arama en fazla ⌊log₂ 10⁶⌋ + 1 = 20 yoklama yapardı.

9. bas = 1.500.000.000 ve son = 1.600.000.000 iken Java'da (bas + son) / 2 ve bas + (son - bas) / 2 ne verir?

   Cevap

   Gerçek toplam 3.100.000.000'dir ve 2³¹ − 1'i aşar. int toplamı 3.100.000.000 − 2³² = −1.194.967.296 olur; ikiye bölünce −597.483.648 çıkar ve dizi[orta] erişimi ArrayIndexOutOfBoundsException fırlatır. Güvenli yazım 1.500.000.000 + 50.000.000 = 1.550.000.000 verir.

3.13İleri okuma

• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 3.1 ve 3.4: sıralı dizide ikili aramayla çalışan bir sembol tablosunu ve hash tablolarını (ayrı zincirleme, doğrusal yoklama) Java koduyla ve deneysel ölçümlerle anlatır.
• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2. baskı, 1998), Kesim 6.1, 6.2.1 ve 6.4: bekçili aramayı, ikili aramanın tarihini ve doğrusal yoklama formüllerinin çıkarılışını ayrıntılı biçimde verir.
• J. Bentley, Programming Pearls (2. baskı, 2000), 4. ve 5. kesimler: ikili aramanın doğru yazılmasını ve doğruluğunun gerekçelendirilmesini örnek olarak işler.
• J. Bloch, “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, 2 Haziran 2006: orta hesabındaki taşma hatasının Java kütüphanesinde nasıl fark edildiğini anlatan kısa bir yazı.

3.14Kaynaklar

1. J. L. Bentley, A. C. Yao, “An Almost Optimal Algorithm for Unbounded Searching”, Information Processing Letters 5(3), 1976.
2. J. Bentley, Programming Pearls, 2. baskı, Addison-Wesley, 2000.
3. J. Bloch, “Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog, 2006.
4. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 2.3, 11).
5. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2. baskı, Addison-Wesley, 1998.
6. Y. Perl, A. Itai, H. Avni, “Interpolation Search — A Log Log N Search”, Communications of the ACM 21(7), 1978.
7. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Bölüm 3.1 İkili arama, 3.4 Hash tabloları).
8. B. Shneiderman, “Jump Searching: A Fast Sequential Search Technique”, Communications of the ACM 21(10), 1978.

İlgili sayfalar: Bölüm 3 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.