İkili axtarış bir sıra bir element tapmaq üçün ən asan yollarından biridir

Tez-tez proqramçılar, hətta yeni başlayanlar, müəyyən bir nömrə tapmaq lazımdırsa, bir neçə ədəd var. Bu kolleksiya bir sıra deyilir. Bunun içərisində doğru element tapmaq üçün bir çox yol var. Ancaq aralarında ən sadə axtarış ikili axtarışdır. Metod nədir? İkili axtarışın necə həyata keçirilməsi lazımdır? Pascal belə bir proqramı təşkil etmək üçün ən sadə bir mühitdir, beləliklə biz bunu öyrənmək üçün istifadə edəcəyik.

Birincisi, bu üsulun üstünlüklərinin nə olduğunu təhlil edəcəyik, buna görə anlaya bilərik ki, Bu mövzunu öyrənməkdə nədir? Beləliklə, ən azı 100000000 elementin ölçüsü olan bir sıra var, güman ki, müəyyən bir tapmaq lazımdır. Əlbəttə ki, bu problem asanlıqla sadə bir linear axtarış yolu ilə həll oluna bilər ki, burada istədiyimiz elementi ardıcıl olaraq olanlarla müqayisə etmək üçün bir loop istifadə edirik. Məsələ ondan ibarətdir ki, bu ideyanın həyata keçirilməsi çox vaxt aparacaq. Sadə bir Paskal proqramında bir neçə prosedur və əsas mətnin üç xətti ilə fərq etməyəcəksiniz, lakin bir çox dallanma və yaxşı funksionallıq ilə daha çox və ya daha az böyük layihələrə başlamış olduğunuzda, hazır proqram çox uzun yüklənəcəkdir. Xüsusilə kompüter pis performansa sahibdir. Buna görə də, axtarış müddətini ən azı iki dəfə azaldan ikili axtarış var.

Belə ki, bu üsulun prinsipi nədir? Dərhal, ikili axtarış heç bir sıra içində deyil, yalnız sıralanan nömrələr qrupunda işlədilməsini deməkdir. Hər bir növbəti addımda arrayın orta elementi götürülür (element nömrəsinə istinad). İstədiyiniz rəqəm orta hesabla daha çox olduqda, solda olan hər şey, yəni ortalama elementdən az, atılacaq və orada axtarışa bilməz. Əksinə, sağdan gələn nömrələr arasında orta hesabla azdırsa, onları axtarmaq edə bilməzsiniz. Sonra, ilk element bütün ardıcıllığın orta elementi olacaq və sonuncu sonuncu olacaq yeni bir axtarış sahəsi seçəcəyik. Yeni sahənin ortalama sayı bütün seqmentin 1/4 hissəsini təşkil edəcək, yəni (son element + bütün arrayin orta elementi) / 2. Yenə də, eyni əməliyyat həyata keçirilir - array orta ədədi ilə müqayisə. İstənilən dəyər orta hesabla azdırsa, sağ tərəfi atın və bu orta element tapılıncaya qədər işləyin.

Əlbəttə, nümunəyə baxmaq üçün ən yaxşı yoldur ikili axtarış necə yazılır. Burada hər kəs üçün Pascal uyğun - versiyası vacib deyil. Sadə bir proqram yazaq.

Bu, 1-dən h adlı "kütləvi" bir array olacaq, "niz", "verh" adlı üst sütun, orta axtarış elementi "sredn" olan aşağı bir axtarış sərhədini ifadə edən dəyişən; Və lazımlı sayı "isk" dir.

Beləliklə, əvvəlcə axtarış aralığının yuxarı və aşağı sərhədlərini təyin edin:

Niz: = 1;
Verh: = h + 1;

Sonra alt "üst sərhədi daha az isə" dövrü təşkil:

Niz Başlayın

Hər bir addımda seqmenti 2:

Sredn: = (niz + verh) div 2; {Qalan hissəni ayırdığımız üçün div funksiyasını istifadə edin}

Hər dəfə bir çek keçiririk. Ortalama istənilənə bərabərdirsə, istədiyimiz element artıq olduğu üçün dövrü kəsəcəyik:

İf sredn = isk sonra break;

Serialın orta elementi aradığımızdan daha böyük olarsa, biz sol tərəfi atırıq, yəni orta elementi yuxarı sərhədi təyin edirik:

Əgər massiv [sredn]> isk isə verh: = sredn;

Və əksinə, əgər biz aşağı həddə etsək:

Else niz: = sredn;
End;

Bütün bunlar proqramda olacaq.

İkili üsulun praktikada necə görünəcəyini təhlil edək. 1, 3, 5, 7, 10, 12, 18 kimi bir array edin və onda 12 sayını axtarın.

Ümumiyyətlə, bizdə 7 element var, beləliklə orta dördüncü, onun dəyəri 7 olacaq.

12-dən 7-dən çox olduğundan, 1,3 və 5 elementləri atılmalıdır. Daha sonra 4 ədədi qaldıq, 4-ü qalan 2-dir. Beləliklə, yeni orta element 10 olacaq.

12-dən 10-dan çox olduğundan, biz 7-i atırıq. Yalnız 10, 12 və 18-i qalır.

Burada orta element 12-dir, bu, lazım olan nömrədir. Vəzifəsi tamamlanıb - 12 nömrə tapılıb.