Algoritma nedir? Aslında her gün kullanıyorsun!
Sabah kalkıyorsun, yüzünü yıkıyorsun, kahvaltını yapıyorsun, okula gidiyorsun. Farkında olmadan kusursuz bir algoritma uyguladın bile.
Yazıyı oku
Sıralı olmak şart
İ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.
Kart örneği
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.
Kütüphane benzetmesi
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.
Neden hızlı?
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.
Bulunmayan değer
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.
Sırasız kart tuzağı
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.
Kendi turun
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?