Bir deste numaralı kart küçükten büyüğe dizilmişse, aradığın sayıyı bulmak için baştan tek tek bakman gerekmez. Ortadaki kart sana hangi yarıya yönelmen gerektiğini söyler.
Sıralı listede ortadan bakmak her adımda arama alanını yarıya indirebilir. Kod Kâşifi için üretilen yapay zekâ illüstrasyonu.
Otuz bir kartta hangi soruyu sorarsın?
Arkadaşın birden otuz bire kadar sıralanmış kartlardan birini seçiyor. Her kartı baştan okuyabilir veya önce ortadaki değeri sorabilirsin. Ortadaki on altıysa ve hedef daha büyükse, ilk yarıda olamayacağını bilirsin. Tek bir karşılaştırma birçok seçeneği elemiş olur. İkili aramanın gücü bu açık çıkarımdan gelir. Rastgele şanslı tahmin yapmak yerine sıralı düzenin verdiği bilgiyi kullanırsın.
İkili arama, düzenli sıralanmış öğeler üzerinde çalışır. Ortadaki değere bakarsın; aradığın sayı küçükse sağ yarıyı, büyükse sol yarıyı elersin. Her adımda adayların yaklaşık yarısı kalır. Liste sıralı değilse bu çıkarım geçerli olmaz. Elemenin dayanağı, bu sıranın bütün kalan değerler için geçerli olmasıdır.
Sözlükte bir kelimeyi ararken ortalara açıp kelimenin önce mi sonra mı geldiğine bakarsın. Sonra kitabın yarısını elersin. Numara kartlarında da aynı karşılaştırma işe yarar. Her adımda bütün kartları yeniden saymak yerine kalan aralığı küçültmek önemlidir. Hangi yarıyı seçtiğinin gerekçesini her tur açık söyleyebilirsin.
Sıralamanın yönü de belli olmalıdır. Küçükten büyüğe listede hedef ortadan küçükse sağ taraf elenir. Büyükten küçüğe listede yön kararı değişir. Ortada olma konum, hedef değerden büyük olma ise karşılaştırma bilgisidir. İkisini karıştırmamak gerekir. Programın kullandığı sıra kuralı hangi öğelerin önce ve sonra geldiğini açıkça tanımlar. Arama, bu kuralla tutarlı olduğu sürece eleme gerekçesi geçerli kalır.
Kalan aralık her turda küçülür
1'den 31'e kadar numaralı kartları sıraya diz ve 23'ü ara. Ortadaki 16'ya bak: 23 daha büyük, demek ki 1 ile 16 arasını eleyebilirsin. Kalan aralığın ortası 24'tür; bu kez 23 daha küçük olduğu için 24 ile 31 arasını ele. Sonraki ortalar 20, 22 ve 23 olur. Beş karşılaştırmayla hedefe ulaşırsın. Her adımda yalnızca kalan aralığı incelemek önemli.
İlk karşılaştırmadan sonra bütün listeyi yeniden ikiye bölmezsin. Artık sadece kalan aralığın ortasına bakarsın. Başta sol sınır ilk, sağ sınır son kart olabilir. Hedef orta değerden büyükse sol sınır ortanın sağına taşınır; küçükse sağ sınır ortanın soluna gelir. Eşitse bulundu dersin. Bu üç durumun açık olması, hem gereksiz karşılaştırmayı hem de aralığın yanlış güncellenmesini azaltır.
Bir kâğıt şeridinde elenen kısmı kapatmak, adayların nasıl azaldığını görünür kılar. Hedefin kapatılan tarafta bulunmamasına dair gerekçeyi her tur söyle: kalan değerler sıralı ve bu taraftakiler hedefe göre küçük. Gerekçe olmadan yarıyı silmek ikili arama değildir. Hangi bilginin eleme kararını mümkün kıldığını anlamak, başka algoritmaların neden belirli ön koşul istediğini öğrenmeye de yardım eder.
Kalan aralıkta çift sayıda kart varsa iki orta aday bulunabilir. Uygulama birini tutarlı biçimde seçebilir. Amaç her tur tam eşit iki parça yapmak zorunda olmak değildir; yaklaşık yarıya indirmek yeterlidir. Bu nedenle son tek kart da kontrol edilmelidir. Ortayı bulma kararı ile sınırları güncelleme kararı birlikte çalışır. Birini yanlış tarif etmek bazı hedeflerin atlanmasına veya aynı kartın tekrar tekrar incelenmesine neden olabilir.
Neden tek tek aramaktan farklı?
Bir listede binlerce öğe varsa tek tek bakmak çok zaman alabilir. İkili aramada her karşılaştırma kalan bölümü küçültür; binlerce seçenek birkaç düzine adımdan çok daha az sayıda adımda bulunabilir. Liste büyüdükçe bu fark daha belirgin olur. Önemli fark, aralık büyüklüğünün her turda nasıl azaldığıdır.
Otuz bir kartlık düzende uygun karşılaştırmalarla en fazla beş turda bir hedef bulunabilir; altmış üç kart için altı tur yeterli olabilir. Liste yaklaşık iki kat büyürken en kötü tur sayısı yalnızca bir artar. Bu, baştan taramada her yeni kartın sıraya yeni olası iş eklemesinden farklıdır. Sayıları kâğıt üzerinde katlayarak liste büyüklüğü ile karşılaştırma sayısının aynı hızda büyümediğini görebilirsin.
Ancak kartların ortasına ulaşmak için hepsini tek tek sayman gerekiyorsa başka bir iş yükü doğar. Bilgisayarda diziler, belirli konumdaki öğeye doğrudan erişim sağlar; bütün veri yapıları aynı erişim özelliğini taşımaz. Basit kâğıt oyununda karşılaştırma sayısını ölçersin. Gerçek programın bütün süre hesabı, verinin nasıl tutulduğunu ve ortadaki öğeye nasıl ulaşıldığını da içerir. Bir ölçünün azalması bütün maliyetin tek başına açıklandığı anlamına gelmez.
Aynı sıralı listede birçok arama yapmak yararlı olabilir. Sırasız listede yalnızca tek hedef arıyorsan önce sıralamaya harcanacak iş de düşünülür. İkili arama her koşulda otomatik en iyi seçim diye söylenmez. Liste zaten sıralı mı, kaç arama yapılacak ve değerler sık değişiyor mu? Algoritmanın uygunluğu problem koşullarına bağlıdır. Güçlü bir yöntem, ön koşullarını bildiğinde daha doğru kullanılır.
Hedef yoksa nasıl durursun?
Aranan sayı listede yoksa da arama durabilir. Ortadaki kartlardan gelen karşılaştırmalar aralığı boşaltır; bu, sayının bulunmadığını gösterir. Program yalnızca 'bulundu' dememeli, gerekirse aralığın boşaldığını da anlamalıdır. Böylece olmayan kartı sonsuza kadar aramaz. Bulunamadı sonucunu göstermek, aramanın hedefini dürüst biçimde tamamlar.
Kartlar karışık duruyorsa ortadaki karta bakıp hangi yarının eleneceğine karar veremezsin. Arama öncesinde sıralamak gerekebilir, ama sıralamanın da bir maliyeti vardır. Tek arama yapacaksan baştan taramak kolay olabilir; çok arama yapacaksan sıralı tutmak avantaj sağlayabilir. Ön hazırlıkla arama süresini iki ayrı iş olarak değerlendirebilirsin.
İki, dört, altı ve sekiz değerleri olan liste içinde beşi ara. Ortadaki karşılaştırmalar seni dört ile altı arasındaki boşluğa götürebilir. Hiçbir kart beş değildir; kalan aralık sonunda boşalır. Bu, daha fazla şans beklemen gerektiğini söylemez. Algoritmanın bulunamadı sonucu da geçerli bir çıktıdır. Arama koşulunun boş aralığı fark etmesi, olmayan öğeyi sonsuza kadar aramamayı sağlar.
Ortayı eledikten sonra aynı orta kartı tekrar aday tutmak aralığı küçültmeyebilir. Örneğin iki kart kaldığında yanlış sınır güncellemesi aynı karşılaştırmayı sürekli döndürebilir. Bu yüzden her turda ya hedef bulunmalı ya da aday sayısı gerçekten azalmalıdır. Kâğıt kaydına sol ve sağ sınırları yazmak bu sorunu görünür kılar. Bir programın durmuş gibi görünmesi, bu tür bir tekrar kuralından kaynaklanabilir.
Listede aynı değer birden fazla kez bulunursa temel arama bunlardan birini bulabilir. İlk veya son kopyayı istiyorsan ek kural gerekir. Bulundu sonucunun anlamını belirlemek önemlidir: bir eşleşme yeterli mi, yoksa bütün konumlar mı aranıyor? Aynı algoritma adı farklı görevleri kendiliğinden tamamlamaz. Yeni koşul, sınır güncelleme ve durma davranışını yeniden düşünmene neden olabilir. Sorunun kapsamı yöntemin ayrıntısını etkiler.
Gerekçesi yazılan bir kart oyunu
Arkadaşın 1 ile 63 arasında bir sayı seçsin. Ortadaki numarayı sor; hedefle aynıysa dur, değilse hangi yarıyı elediğini kâğıda yaz. Kalan aralıkta aynı işlemi tekrar et. En son tek kart kalırsa o kartın hedef olup olmadığını kontrol et. Aralık boşalırsa hedef listede yoktur. Kaç karşılaştırma yaptın? Sıralı kartların verdiği ipucu olmasaydı stratejin nasıl değişirdi?
Her tur için üç not tut: orta değer, karşılaştırma sonucu ve kalan aralık. Arkadaşın son kayıttan bir sonraki soruyu çıkarabiliyor mu? Eğer çıkarmak için ek tahmin gerekiyorsa sınırlar eksik yazılmış olabilir. Sonra bir kartın yerini bozup aynı stratejiyi dene. Hedef yanlışlıkla elenebilir; bu başarısızlık sıralamanın neden zorunlu olduğunu gösterir. Başarılı tur kadar ön koşulu bozan tur da yöntemi öğretir.
Bir sonraki görevde kitap başlıklarını alfabetik sıraya koyarak aynı düşünceyi denersin. Karşılaştırma sayıdan harf sırasına geçer, ama kalan aralığı daraltma fikri korunur. Harf sırası ve dil kuralları açık olmalıdır; farklı sıralama beklemek yanlış eleme yaratabilir. İkili aramayı öğrenmek yalnızca ortaya bak sözünü hatırlamak değildir. Düzenin sunduğu bilgiyi, elemenin gerekçesini ve sonucun ne zaman kesin olduğunu birlikte anlamaktır.
1–31 arasındaki sıralı kartlarda 23'ü ararken her karşılaştırmayı kaydedelim. Bu örnekte çift sayıda kart kaldığında küçük olan orta değer seçiliyor.
İkili aramanın beş karşılaştırması
Tur
İncelenen aralık
Orta değer
Karar
1
1–31
16
23 büyük: 17–31 kalır
2
17–31
24
23 küçük: 17–23 kalır
3
17–23
20
23 büyük: 21–23 kalır
4
21–23
22
23 büyük: yalnız 23 kalır
5
23–23
23
Eşit: bulundu
Tablonun karar sütununu kapat. Her orta değerden sonra kalan aralığı kendin yaz.
Aynı kartlarla 8'i ara. Kontrol ettiğin orta değerleri sırayla kaydet.
Son olarak yalnız çift numaralı kartlarla 9'u ara. Olmayan bir hedefi aramayı ne zaman bırakacağını açıkla.
Sonucunu karşılaştır
8 için orta değerler 16 ve 8'dir; iki karşılaştırma yeter. Yalnız çift kartlarda 9 bulunamaz. Kalan aday aralığı boşaldığında 'bulunamadı' sonucuna varırsın; aynı kartı tekrar tekrar kontrol etmezsin.