Kompüterlər, Proqramlaşdırma
İ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,
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
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.
1 | 3 | 5 | 7-ci | 10 | 12 | 18-ci |
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.
7-ci | 10 | 12 | 18-ci |
Burada orta element 12-dir, bu, lazım olan nömrədir. Vəzifəsi tamamlanıb - 12 nömrə tapılıb.
Similar articles
Trending Now