İkili arama, bir dizide bir öğe bulmanın en kolay yollarından biridir.

Çoğu zaman, programcılar, yeni başlayanlar bile,belirli bir sayıyı bulmak için gerekli olan bir sayı kümesi olduğu yüzüne. Bu koleksiyona dizi denir. İçinde doğru unsuru bulmak için birçok yol var. Ancak, aralarında en basit olanı, ikili bir arama olarak kabul edilebilir. Yöntem nedir? Ve ikili arama nasıl uygulanır? Pascal, böyle bir programı organize etmenin en basit aracıdır, bu yüzden çalışma için kullanacağız.

İlk olarak, bu yöntemin avantajlarının ne olduğunu analiz edeceğiz, sonuçta anlayabiliriz,

Bu konunun çalışılmasının amacı nedir? Dolayısıyla, belirli bir tane bulmanız gereken en az 100000000 öğeden oluşan bir dizi olduğunu varsayalım. Tabii ki, bu problem basit bir lineer arama ile kolayca çözülebiliyor, ki bu döngüde istenen elemanı dizi içinde mevcut olanlarla karşılaştırmak için kullanacağız. Sorun şu ki bu fikrin uygulanması çok uzun sürecek. Basit bir Pascal programında, birkaç prosedür için ve ana metnin üç satırıyla, bunu fark etmeyeceksiniz, ancak çok fazla dallanma ve iyi işlevsellik ile daha büyük projeler başlattığınızda, bitmiş program çok uzun süre yüklenecektir. Özellikle bilgisayarın performansının düşük olması durumunda. Bu nedenle, arama süresini en az iki kez azaltan ikili bir arama var.

Yani, bunun çalışma prensibi nediryöntemi? İkili aramanın herhangi bir dizide çalışmadığı, ancak yalnızca sıralanmış bir sayı kümesinde söz edilmesine değer. Her sonraki adımda, dizinin orta elemanı (eleman numarasına bakarak) alınır. İstenen sayı ortalamanın üzerindeyse, soldaki, yani ortalama elemandan daha az olan her şey atılabilir ve orada aranamaz. Tersine, eğer ortalamanın altındaysa, sağdaki numaralar arasında, onları arayamazsınız. Ardından, tüm dizinin orta elemanının ilk öğe olduğu ve sonuncusunun sonuncu olarak kalacağı yeni bir arama alanı seçeceğiz. Yeni alanın ortalama sayısı tüm segmentin will, yani (son elemanın + tüm dizinin ortalama elemanı) / 2 olacaktır. Yine, aynı işlem gerçekleştirilir - dizinin ortalama sayısı ile karşılaştırma. İstenen değer ortalamanın altındaysa, sağ tarafa atın ve bu orta eleman bulunana kadar aynısını yapın.

Tabii ki, bir ikili aramanın nasıl yazıldığına dair bir örneğe bakmak en iyisidir. Pascal herkes için uygundur - versiyon önemli değil. Basit bir program yazalım.

1'den h'ye kadar bir dizi olacak."massiv", "niz" olarak adlandırılan alt arama sınırını ifade eden değişken, "verh" olarak adlandırılan üst sınır, aramanın orta öğesi "sredn" dir; ve gerekli sayı "isk".

Bu nedenle, önce arama aralığının üst ve alt sınırlarını atayın:

niz: = 1;
verh: = h + 1;

Ardından "alt kısım üst limitin altındayken" döngüsünü düzenleriz:

Niz <verh - 1 yaparken
başlamak

Her adımda, segmenti 2'ye bölün:

sredn: = (niz + verh) div 2; {div işlevini kullanın, çünkü kalanını böleriz}

Her kontrol yaptığımızda. Ortalama, istenen olana eşitse, istenen eleman zaten bulunduğundan, döngüyü durdururuz:

sredn = isk sonra kır;

Dizinin ortalama elemanı, aradığımızdan daha büyükse, sol tarafı atın, yani orta elemanı üst sınıra atarız:

eğer massiv [sredn]> isk sonra verh: = sredn;

Ve tam tersine, o zaman alt sınırı yaparız:

else niz: = sredn;
uç uca gelir;

Bu programda olacak hepsi bu.

İkili yöntemin pratikte nasıl görüneceğini analiz edeceğiz. Böyle bir dizi alırız: 1, 3, 5, 7, 10, 12, 18 ve 12 numarayı ararız.

Toplamda, 7 elementi var, yani ortalama dördüncü, değeri 7 olacak.

12'den fazla, 7, 1.3 ve 5 element yana, iptal edebilir. Sonra numarayı 4 var, 4/2 hiçbir kalıntı 2. Yani, yeni bir eleman 10 ortalama olacaktır.

12, 10'dan fazla olduğu için, 7. atın. Sadece 10, 12 ve 18 kaldı.

Burada orta eleman zaten 12, bu gerekli sayıdır. Görev tamamlandı - 12 numara bulundu.