Ორობითი ძებნა ერთ - ერთი ყველაზე იოლი გზა ელემენტს მასივი

საკმაოდ ხშირად, პროგრამისტების, თუნდაც დამწყებთათვის, წინაშე, რომ არ არსებობს კომპლექტი ნომრები, რომელიც უნდა იპოვოს კონკრეტული რაოდენობა. ეს არის ეს კოლექცია მოუწოდა მასივი. და მოვძებნოთ ელემენტი, არსებობს უამრავი გზა. მაგრამ ყველაზე მარტივი მათგანი შეიძლება ჩაითვალოს ორობითი ძებნა მარჯვენა. რა არის ეს მეთოდი? და როგორ უნდა განახორციელოს ორობითი ძებნა? Pascal არის მარტივი გარემო ორგანიზაციის ასეთი პროგრამა, ასე რომ, ჩვენ ვიყენებთ მას სწავლა.

პირველ რიგში, ანალიზი, რა უპირატესობა ამ მეთოდით, ეს ასე ჩვენ შეგვიძლია გავიგოთ, რა არის წერტილი შესწავლა თემაზე. ასე რომ, მოდით მასივში განზომილება მინიმუმ 100000000 ელემენტები, რომლებიც უნდა გამოძებნოს. რა თქმა უნდა, ეს პრობლემა შეიძლება ადვილად მოგვარდება მარტივი ხაზოვანი ძებნა, რომელშიც ჩვენ ვიყენებთ ციკლი შედარება საჭირო ელემენტს ყველა იმ მასივი. პრობლემა ის არის, რომ ამ იდეის განხორციელება მიიღებს ძალიან ბევრი დრო. მარტივი Pascal პროგრამა რამდენიმე მკურნალობა, და სამ ძირითად ტექსტში, თქვენ არ შეამჩნია, მაგრამ როდესაც ჩვენ მოვიდა მეტნაკლებად დიდი პროექტების დიდი რაოდენობით ფილიალები და კარგი ფუნქცია, პროგრამა იქნება მზად უნდა იყოს დატვირთული ძალიან დიდი ხნის განმავლობაში. მით უმეტეს, თუ კომპიუტერი არის სუსტი შესრულება. აქედან გამომდინარე, არ არის ორობითი ძებნა, რაც ამცირებს ძებნის დროს ორჯერ მაინც.

ასე რომ, რა არის სამუშაო პრინციპი ეს მეთოდი? დაუყოვნებლივ უნდა ვთქვა, რომ ბინარული ძებნის მუშაობს არ არის არანაირად მასივი, მაგრამ მხოლოდ დახარისხებული კომპლექტი ნომრები. ამავე ყოველი ნაბიჯი შუა ელემენტს array (რაც იმას ნიშნავს, რაოდენობის ელემენტი). თუ საჭირო რაოდენობის მეტია საშუალო, მაშინ ყველაფერი, რაც დარჩა, რომელიც ნაკლებია, ვიდრე საშუალო საკანში, შეიძლება განადგურდეს და არ უნდა გამოიყურებოდეს არსებობს. პირიქით, თუ ნაკლები საშუალო - მათ შორის, ნომრები უფლება, თქვენ ვერ ვეძებოთ. აირჩიეთ ახალი ძიების ადგილი, სადაც პირველი ელემენტი იქნება შუა ელემენტს მთელი მასივი, და ბოლო და ბოლო ნება. საშუალო რაოდენობა new სფეროში იქნება ¼ ყველა სეგმენტი, რომ არის, (ბოლო ელემენტს + შუა ელემენტს მთელი მასივი) / 2. ისევ და ისევ, იგივე ოპერაცია - შედარებით საშუალო რაოდენობა მასივი. თუ სამიზნე ღირებულება ნაკლებია, ვიდრე საშუალო, ჩვენ უარს მარჯვენა მხარეს, და ასევე უნდა გავაკეთოთ შემდეგი, დღემდე ამ შუა ელემენტს არ არის სასურველი.

რა თქმა უნდა, ეს არის საუკეთესო შევხედოთ მაგალითს, თუ როგორ წერენ ორობითი ძებნა. Pascal აქ ჯდება ვინმეს - მობილური არ არის მნიშვნელოვანი. მოდით დავწეროთ მარტივი პროგრამა.

ეს არის მასივი 1 სთ სახელწოდებით "massiv", ცვლადი მითითებით ქვედა საზღვრის ძიება, სახელწოდებით "Niz", ზედა ზღვარი, სახელწოდებით "Verh", საშუალო საძიებო ტერმინი - "sredn"; და საჭირო რაოდენობის - "ISK".

ასე რომ, პირველი, მივანიჭოთ ზედა და ქვედა ზღვარი სპექტრი ძებნა:

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

მაშინ ორგანიზება ციკლიდან "სანამ ბოლოში ნაკლებია, ვიდრე ზედა ზღვარი":

მიუხედავად იმისა, რომ Niz დაიწყოს

თითოეულ ნაბიჯს, ჩვენ გაყოფა სეგმენტი 2:

sredn: = (Niz + Verh) div 2; {გამოიყენეთ ფუნქცია div, რადგან გათიშე გარეშე დარჩენილი}

ყოველ დროს, მიმოხილვა. იმის გამო, რომ ნივთი უკვე ნაპოვნია, თუ საშუალო სასურველი შეუშალოს ციკლი:

თუ sredn = ISK შემდეგ შესვენება;

თუ შუა ელემენტს მასივი სასურველზე მეტია, გაუქმება მარცხენა მხარეს, რომ არის, ზედა ზღვარი საშუალო დანიშნოს ელემენტი:

თუ მასივი [sredn]> ISK მაშინ Verh: = sredn;

და თუ პირიქით, ეს ქმნის ქვედა საზღვრის:

სხვა Niz: = sredn;
დასრულდება;

ეს არის ის, რომ იქნება ამ პროგრამაში.

მოდი, განვიხილოთ, თუ როგორ გამოიყურება ორობითი მეთოდის პრაქტიკაში. მიგვაჩნია, რომ ეს მასივი: 1, 3, 5, 7, 10, 12, 18 და ის შეეცდება რიცხვი 12.

საერთო ჯამში ჩვენ გვაქვს 7 ელემენტები, ასე იქნება მეოთხე საშუალო ღირებულება 7.

მას შემდეგ, რაც უფრო მეტია, ვიდრე 12, 7, 1.3 და 5 ელემენტები, ჩვენ შეგვიძლია გაუქმება. შემდეგ ჩვენ მივიღეთ ნომერი 4, 4/2 ნარჩენების 2. ასე რომ, ახალი ელემენტი იქნება საშუალოდ 10.

მას შემდეგ, რაც 12 მეტი 10, ჩვენ გაუქმება 7. რჩება მხოლოდ 10, 12 და 18.

აქ, შუა ელემენტს არის უკვე 12, ეს არის საჭირო რაოდენობის. ეს დავალება დასრულებულია - ნომერი 12 ი.