[მუსიკის დაკვრა] 

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

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

თუ ეს არის სრული mix up, ჩვენ არ შეგვიძლია უბრალოდ გარეთ მხრივ გაუქმება ნახევარში ელემენტები, იმიტომ, რომ ჩვენ არ ვიცით, რა ჩვენ გაქვს. მაგრამ, თუ მასივი დალაგებულია, ჩვენ შეგვიძლია ამის გაკეთება, იმიტომ, რომ ჩვენ ვიცი, რომ ყველაფერი დარჩა, სადაც ჩვენ გაკეთებული არის უნდა იყოს დაბალია, ვიდრე მნიშვნელობა ჩვენ ამჟამად. და ყველაფერი უფლება, სადაც ჩვენ ვართ უნდა იყოს მეტი ღირებულების ჩვენ გაკეთებული ეძებს. 

რა არის pseudocode ნაბიჯები ორობითი ძებნა? ჩვენ ვიმეორებ ეს პროცესი მანამ, სანამ array ან, როგორც ჩვენ გაგრძელება მეშვეობით, ქვე მასივები, პატარა ცალი ორიგინალური მასივი, ზომა 0. გამოთვალოთ შუაში მიმდინარე sub მასივი. 

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

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

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

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

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

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

ასე რომ, ჩვენ გამოვთვალოთ შუაში მიერ დასძინა 0 + 14 გაყოფილი 2; საკმაოდ მარტივია შუაში. და შეიძლება ითქვას, რომ შუაში არის 7. ასე რომ, 15, რასაც ჩვენ ვეძებთ? არა, ეს ასე არ არის. ჩვენ ვეძებთ 19. მაგრამ ჩვენ ვიცით, რომ 19 არის უფრო მეტი ვიდრე ის, რაც ჩვენ აღმოვაჩინეთ შუა. 

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

და ახლა, ჩვენ წავიდეთ ამ ერთხელ. ჩვენ გამოვთვალოთ ახალი შუაში. 8 + 14 22, გაყოფილი 2-11. ეს არის ის, რაც ჩვენ ვეძებთ? არა, ეს ასე არ არის. ჩვენ ვეძებთ ღირებულება, რომელიც არის ნაკლებია, ვიდრე ის, რაც ჩვენ უბრალოდ ი. ასე რომ, ჩვენ ვაპირებთ გავიმეორო პროცესი კიდევ ერთხელ. ჩვენ ვაპირებთ, რომ შეიცვალოს ბოლოს წერტილი იყოს მხოლოდ, რომ მარცხნივ შუაში. ასე რომ, ახალი ბოლომდე წერტილი ხდება 10. და ახლა, რომ ეს არის მხოლოდ ნაწილი მასივი ჩვენ უნდა დასალაგებლად მეშვეობით. ასე რომ, ჩვენ უკვე აღმოფხვრილი 12 15 ელემენტებს. ჩვენ ვიცით, რომ თუ 19 არსებობს მასივი, ის უნდა არსებობდეს სადღაც შორის ელემენტი ნომერი 8 და ელემენტს ნომერი 10. 

ასე რომ, ჩვენ გამოვთვალოთ ახალი შუაში კვლავ. 8 + 10 18, გაყოფილი 2-9. და ამ შემთხვევაში, გამოიყურება, სამიზნე არის შუა. ჩვენ აღმოვაჩინეთ, რაც ჩვენ ვეძებთ. ჩვენ შეგვიძლია შეწყვიტოს. ჩვენ წარმატებით დასრულდა ორობითი ძებნა. ყველა უფლება. ასე რომ, ჩვენ ვიცით, რომ ეს ალგორითმი მუშაობს თუ სამიზნე სადღაც შიგნით მასივი. ნიშნავს თუ არა ეს ალგორითმი მუშაობს თუ სამიზნე არ არის მასივი? მოდით, დავიწყოთ ეს კიდევ ერთხელ, და ამ დროს, მოდით შევხედოთ ელემენტს 16, რომელიც ვიზუალურად, ჩვენ ვხედავთ, არ არსებობს სადმე მასივი. 

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

რა არის ნაბიჯი პირველი? გამოთვალოთ შუაში მიმდინარე მასივი. რა არის შუაში მიმდინარე მასივი? ისე, ეს 7, არა? 14 + 0 იყოფა 2 7. 15 ის, რასაც ჩვენ ვეძებთ? No. ეს არის საკმაოდ ახლოს, მაგრამ ჩვენ ვეძებთ დიდი მნიშვნელობა ოდნავ დიდია, ვიდრე ეს. 

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

ახლა, ჩვენ ვიმეორებთ დამუშავებას კიდევ ერთხელ. გამოთვალეთ ახალი შუაში. 8 + 14 22, გაყოფილი 2-11. 23 ის, რასაც ჩვენ ვეძებთ? სამწუხაროდ, არ არსებობს. ჩვენ ვეძებთ მნიშვნელობა რომ ნაკლებია 23. ასე რომ, ამ შემთხვევაში, ჩვენ ვაპირებთ შეცვალოს ბოლომდე წერტილი უნდა იყოს მხოლოდ მარცხნივ მიმდინარე შუაში. მიმდინარე შუაში არის 11, და ასე რომ, ჩვენ დავსახეთ ახალი ბოლომდე წერტილი მომდევნო ჯერზე ჩვენ ეს პროცესი 10. 

კიდევ ერთხელ, ჩვენ გავლა პროცესი კიდევ ერთხელ. გამოთვალეთ შუაში. 8 + 10 იყოფა 2 9. 19 ის, რასაც ჩვენ ვეძებთ? სამწუხაროდ, არ არსებობს. ჩვენ ჯერ კიდევ ეძებს რიგი ნაკლებია. ასე რომ, ჩვენ შეიცვლება ბოლომდე წერტილი ამ დროს უნდა იყოს მხოლოდ, რომ მარცხნივ შუაში. შუაში არის გაკეთებული 9, ასე ბოლომდე წერტილი იქნება 8. და ახლა, ჩვენ უბრალოდ ეძებს განთავსებულია ერთ ელემენტს მასივი. 

რა არის შუაში ამ მასივი? ისე, ეს იწყება 8, ეს მთავრდება 8, შუაში არის 8. ის არის, რომ ის, რაც ჩვენ ვეძებთ? ნუთუ ჩვენ ვეძებთ 17? არა, ჩვენ ვეძებთ 16. ასე რომ, თუ ის არსებობს მასივი, ის უნდა არსებობდეს სადღაც მარცხნივ, სადაც ამჟამად არიან. ასე რომ, რასაც ჩვენ ვაპირებთ, რომ გავაკეთოთ? ისე, ჩვენ ვაყენებთ ბოლომდე წერტილი უნდა იყოს მხოლოდ მარცხნივ მიმდინარე შუაში. ასე რომ, ჩვენ შეიცვლება ბოლომდე წერტილი 7. ნუ ხედავთ რა უბრალოდ აქ მოხდა, თუმცა? შეხედეთ აქ ახლა. 

დაწყება არის უფრო მეტი, ვიდრე ბოლომდე. ეფექტურად, ორი მთავრდება ჩვენი მასივი გადაკვეთა, და დაწყების წერტილი არის მას შემდეგ, რაც ბოლომდე წერტილი. ისე, რომ არ არანაირი აზრი, არა? ახლა, რა შეგვიძლია ვთქვათ, რომ ჩვენ აქვს sub მასივი ზომა 0. და კიდევ ჩვენ მიღებული ამ ეტაპზე, ჩვენ ახლა გარანტიას გაძლევთ, რომ ელემენტს 16 არ არსებობს მასივი, იმის გამო, რომ საწყის ეტაპზე და ბოლოს წერტილი გადმოკვეთა. ასე რომ, ეს არ არის. ახლა, რომ ეს არის ოდნავ განსხვავებული, ვიდრე დაწყების წერტილი და ბოლოს აღვნიშნო, რომ იგივე. თუ ჩვენ უკვე ეძებს 17, ეს იქნებოდა უკვე მასივი, და დაწყების წერტილი და ბოლოს წერტილი, რომ ბოლო მცდელობაა ადრე იმ რაოდენობა გადმოკვეთა, ჩვენ არ გამოვლინდა 17 არსებობს. ეს მხოლოდ მაშინ, როდესაც ისინი გადაკვეთენ, რომ ჩვენ შეგვიძლია გარანტიას გაძლევთ, რომ ელემენტს არ არსებობს მასივი. 

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

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

ასე რომ, უარეს იმ შემთხვევაში, ორობითი ძებნა გადის ჟურნალის n, რომელიც არსებითად უკეთესი ვიდრე სწორხაზოვანი ძებნა, უარეს შემთხვევაში. საუკეთესო შემთხვევაში, ორობითი ძიება ეშვება omega 1. ასე რომ ორობითი ძებნა ბევრი უკეთესად ხაზოვანი ძებნა, მაგრამ თქვენ უნდა გაუმკლავდეთ პროცესში დახარისხება თქვენი მასივი სანამ შეუძლია ბერკეტი ძალა ორობითი ძებნა. 

მე Doug Lloyd. ეს არის CS 50.