İkili arama - en kolay yollarından biri, dizideki bir öğe bulmak için

Oldukça sık, programcılar, hatta yeni başlayanlar, belirli sayıda bulmak zorundadır sayı kümesi, var olduğu gerçeği ile karşı karşıya. Bu koleksiyon bir dizi olarak adlandırılır olduğunu. Ve öğeleri bulmak için, yollar sayısız vardır. Ama bunların çoğu basit sağda bir ikili arama düşünülebilir. Bu yöntem nedir? Ve nasıl ikili arama uygulamak için? Pascal böyle bir programın düzenlenmesi için en kolay ortamdır, bu yüzden çalışma için kullanırlar.

İlk olarak, analiz, bu yöntemin avantajları nelerdir, bu yüzden anlayabilir, konunun incelenmesinde noktası budur. Yani, bazı bulmalıyız en az 100000000 elemanları, bir boyutu ile bir dizi atalım. Elbette, bu sorunun kolayca biz dizideki olan tüm siteleri ile gerekli öğesi karşılaştırır çevrimi kullanılarak edildiği bir basit doğrusal arama, çözülebilir. Sorun bu düşüncenin uygulanması çok fazla zaman alacak olmasıdır. Birkaç muamele ve ana üç satırlık bir metin haline basit bir Pascal programında, bunu fark olmayacak, ama biz şube ve iyi işlevsellik çok sayıda aşağı yukarı büyük projelerde geldiklerinde, programın çok uzun süre yüklenmek üzere hazır olacaktır. Özellikle bilgisayar zayıf bir performans ise. Bu nedenle, en az iki kez arama süresini azaltan bir ikili arama vardır.

Yani, bu yöntemin çalışma prensibi nedir? Hemen o ikili arama hiçbir dizide değil, sadece bir sayı sıralı sette çalıştığını söylemek gerekir. Dizinin her bir aşama alınan orta eleman da (element sayısını ifade eder). Gerekirse sayı büyükse ortalamasının, o zaman tüm kaldığını, ortalama hücrede azdır, atılacak ve orada bakmamaya. Tersine, ortalamadan daha az ise - sağa Bu numaralar arasında, arama olamaz. Sonra ilk unsur tüm dizinin orta eleman ve son ve son isteği olacak yeni arama alanını seçin. yeni alanın ortalama sayısı hepsi kesimi, (son unsuru + tüm dizi orta eleman) / 2 dörtte olacaktır. Yine aynı işlem gerçekleştirilir - dizi ortalama sayısı ile bir karşılaştırma. Hedef değeri ortalamadan daha az ise, biz sağ tarafını reddetmek ve ayrıca artık bu orta eleman istenilen olmaz kadar bir sonraki yapmak.

Tabii ki, bu ikili arama yazmak için nasıl bir örnek bakmak en iyisidir. Pascal burada kimseye uygun olacaktır - versiyon önemli değildir. Basit bir program yazalım.

Bu isim "massiv" altında h 1 olan bir dizi "verh", ortalama arama terimi adı "niz" adı verilen arama alt sınırını belirten bir değişken, üst limit, - "sredn"; ve gerekli sayıda - "isk".

Yani, önce biz aralık aramanın üst ve alt sınırı atayın:

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

Daha sonra, "alt üst sınırdan daha az olana kadar" döngüsü düzenlemek:

niz başlamak

Her bir adımda, bir bölümü 2 bölerler:

sredn: = (niz + verh) div 2; {Kalanı olmadan bölmek için fonksiyon div kullanım}

Yorumun her zaman. orta isteniyorsa öğe zaten tespit edildiği için, döngüyü yarıda:

іf sredn = ISK sonra kırmak;

İstenen fazla dizinin orta ayağı, sol yan atmak için, yani, ortalama üst sınır elemanı tayin:

Eğer masif [sredn]> ISK sonra verh: = sredn;

Ve tersine, eğer alt sınırını yapar:

Başka niz: = sredn;
uç uca gelir;

Bu programda olacak o kadar.

Bizim uygulamada ikili yöntemini nasıl görüneceğini düşünelim. 1, 3, 5, 7, 10, 12, 18 ve 12 numaralı çalışacaktır: Bu dizi göz önünde bulundurun.

Toplamda 7 elemanlarına sahip, yani orta büyüklük 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 daha büyük olduğu için, 7, sadece 10, 12 ve 18 kalır atın.

Burada, orta eleman zaten 12'dir, gerekli sayıdır. Bu görev tamamlandı - 12 numaraya bulundu.