İkili arama nasıl çalışır?

İkili arama nasıl çalışır? www.yzokul.com.tr

İkili aramanın nasıl çalıştığını bilmek istiyorsun. Kısa yanıt şudur: sıralı verinin ortadaki öğesini kontrol eder ve hedefi bulana kadar alanı sürekli yarıya indirir. Bu yöntem hızlıdır çünkü her kontrolde kalan öğelerin yarısını atar. Yalnızca veri sıralı olduğunda doğru çalışır. Bu sürecin her parçasını ilerleyen sayfalarda öğreneceksin. 1

Verini bir sıra hâlinde dizilmiş öğeler olarak düşün; yan yana konmuş kartlardaki sayılar gibi. Bu sıra, içinde arama yapacağın gruptur. Her kartta bir değer vardır ve kartlar sabit bir düzende dizilmiştir. Sıradaki konumuna göre herhangi bir kartı işaret edebilirsin. Amaç, bu kartlar arasında belirli bir hedef değeri bulmaktır. 2

İkili aramanın çalışması için sıra düzenli olmalıdır, örneğin en küçükten en büyüğe doğru. Bu düzene sıralı veri denir. Bu düzen olmadan yarıya indirme hilesi doğru çalışamaz çünkü hedefin hangi yarıda olduğunu bilemezsin. İkili aramayı kullanmadan önce verinin sıralı olduğunu her zaman kontrol et. Sıralı değilse önce sırala. 3

Somut bir sıralı sıraya bak: 2, 5, 8, 12, 16, 23, 38. Bu sayılar artan düzendedir. 23 sayısını bulmak istediğini varsayalım. Bu sıra senin arama alanındır. 23'ü hızlıca bulmak için ikili aramayı kullanacaksın. Sayıların değer aralıklarının eşit olduğuna dikkat et, ama bu gerekli değildir—yalnızca düzen önemlidir. 4

Ortadaki öğeyi bulmak için öğeleri say ve ortadakini seç. 2, 5, 8, 12, 16, 23, 38 sırasında yedi öğe vardır, yani orta dördüncü öğedir: 12. O ortadaki kart, ikili aramanın ilk baktığı karttır. Öğe sayısı çiftse iki ortadakinden birini seçebilirsin; yöntem yine de çalışır. Ortadaki öğe, sırayı bir sol parçaya ve bir sağ parçaya böler. 5

Hedefini (23) ortadaki değerle (12) karşılaştır. Yanıt üç şeyden biridir: eşit, daha küçük veya daha büyük. Burada 23, 12'den büyüktür. Bu karşılaştırma hangi yarıyı tutacağını söyler. Her öğeyi kontrol etmene gerek yok; karşılaştırma sana yol gösterir. Bu karşılaştırmanın sonucu bir sonraki hamleni belirler. 6

Hedef ortadaki değere eşitse arama biter. Öğeyi tek bir kontrolde bulmuş olursun. Örneğin sırada 12'yi arıyor olsaydın hemen dururdun çünkü 12 ortadadır. Bu en iyi durumdur: hedef tam olarak ortadadır. Sonra öğenin bulunduğunu bildirebilirsin. 7

Hedef ortadaki değerden küçükse ortayı ve sağındaki her şeyi yok sayarsın. Yalnızca sol yarıyı tutarsın. Örneğin sırada 8'i arıyor olsaydın, 8, 12'den küçüktür, bu yüzden 12'yi ve sağındaki tüm sayıları (16, 23, 38) atarsın. Yeni arama alanı 2, 5, 8 olur. Sonra bu daha küçük sırada süreci tekrarlarsın. 8

Hedef ortadaki değerden büyükse ortayı ve solundaki her şeyi yok sayarsın. Yalnızca sağ yarıyı tutarsın. Örneğimizde 23, 12'den büyüktür, bu yüzden 12'yi ve solundaki tüm sayıları (2, 5, 8) atarsın. Yeni arama alanı 16, 23, 38 olur. Sonra bu daha küçük sırada süreci tekrarlarsın. 9

Her kontrol, kalan öğelerin yaklaşık yarısını atar. Aday alan her adımda hızla küçülür. Örneğin 7 öğeyle başlayınca bir kontrolden sonra en fazla 3 öğe kalır. İki kontrolden sonra en fazla 1 öğe kalır. Bu yarıya indirme, ikili aramanın büyük veri kümelerinde bile hızlı olmasının nedenidir. Gereken adım sayısı, her öğeyi kontrol etmeye kıyasla azdır. 10

Kalan yarıyı al ve ortadaki öğesini yeniden bul. Yeni 16, 23, 38 sırasında orta 23'tür. Hedefini (23) 23 ile karşılaştır: eşittirler, yani buldun. Eşit olmasalardı yine uygun yarıyı tutardın. Hedefi bulana kadar ya da öğeler tükenene kadar bu süreci tekrarlarsın. 11

Bir sözlükte kelime bulmayı düşün. Sözlüğü ortaya yakın bir yerden açarsın ve kelimenin o sayfadan önce mi sonra mı geldiğine bakarsın. Sonra uygun yarıyı alıp onun ortasına yakın bir yerden açarsın, kelimeyi bulana kadar tekrarlarsın. İkili arama tam olarak böyle çalışır: her karşılaştırma bir sonraki aramada hangi yarıyı arayacağını söyler. Sözlük alfabetik olarak sıralıdır, tıpkı verinin sıralı olması gerektiği gibi. 12

Arama, ortadaki değer hedefle eşleştiğinde durur. Hiç öğe kalmadığında da durur, bu da hedefin orada olmadığı anlamına gelir. Örneğin 2, 5, 8, 12, 16, 23, 38 sırasında 7'yi ararsan sonunda boş bir alana daralır ve 7'nin olmadığı sonucuna varırsın. Ne zaman duracağını bilmek, sonsuz döngülerden kaçınmak için önemlidir. 13

Yaygın bir hata, sıralı olmayan veride ikili arama kullanmaktır. O zaman yarılar beklediğini içermez ve yanıt yanlış olabilir. Örneğin sıra 12, 2, 38, 5, 16, 8, 23 olsaydı orta 5 olurdu, ama sol yarı tamamen 5'ten küçük değildir. İkili aramayı uygulamadan önce verinin sıralı olduğundan her zaman emin ol. 14

Bir başka hata, önce ortayla karşılaştırmadan bir yarıya atlamaktır. Hangi yarıyı tutacağını sana söyleyen şey karşılaştırmadır. Onu atlarsan yanlış yarıyı seçebilir ve hedefi kaçırabilirsin. Hangi yarıyı atacağına karar vermeden önce hedefi her zaman ortadaki değerle karşılaştır. Bu basit kontrol, yöntemin kalbidir. 15

İkili arama, sıralı verinin ortasını kontrol eder, sonra hedefin olması gereken yarıyı tutar. Alan her adımda yarıya iner, böylece öğeleri hızlı bulur. Verini önce sıralamayı ve her zaman ortayla karşılaştırmayı unutma. Pratikle bu yöntemi herhangi bir sıralı listeye uygulayabilirsin. Verimli arama için güçlü bir araçtır. 16