რობ Bowden: Hi, მე Rob. როგორ უნდა დაასაქმოს ორობითი ძებნა? მოდით გავარკვიოთ. ასე რომ, გაითვალისწინოთ, რომ ძიების ჩვენ ვაპირებთ განახორციელოს რეკურსიული. თქვენ შეიძლება ასევე განახორციელოს ორობითი ძებნა iteratively ასე რომ, თუ თქვენ გააკეთეთ, რომ, რომ შესანიშნავად ჯარიმა. 

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

ახლა, პირველი, რაც პირველი. ჩვენ შეამოწმეთ თუ n უდრის 0, in ასეთ შემთხვევაში ჩვენ დაბრუნების ცრუ. რომ უბრალოდ ვამბობ, თუ ჩვენ ცარიელი მასივი, ღირებულება აშკარად არ ცარიელი მასივი, ასე რომ ჩვენ შეგვიძლია დაბრუნების ცრუ. 

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

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

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

ამ რეკურსიული ზარი მოძიება, ჩვენ ახლა განაცხადა, რომ სიგრძეზე array არის ცენტრიდან. ასე რომ, თუ ჩვენი მასივი იყო ზომა 20 და ჩვენ ჩხრეკა საათზე ინდექსი 10, მას შემდეგ, რაც შუა არის 20 იყოფა 2, ეს ნიშნავს, რომ ჩვენ გავლით 10, როგორც ახალი ხანგრძლივობა ჩვენი მასივი. გახსოვდეთ, რომ როდესაც თქვენ გაქვთ მასივი სიგრძე 10, ეს ნიშნავს, რომ მოქმედი ელემენტები ინდექსების 0 მეშვეობით 9. ასე რომ, ეს არის ის, რაც ჩვენ გვინდა მიუთითოთ ჩვენი ახლდება მასივი - მარცხენა array შუა ელემენტს. 

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

ისევ და ისევ, თუ array იყო ზომა 20 ჩვენ გაყოფა 2 მისაღებად შუა, ასე რომ, შუა არის 10, მაშინ n მინუს შუა აპირებს მოგვცეს 10, ისე 10 ელემენტები მარჯვნივ ცენტრიდან. მაგრამ ჩვენ ასევე გვაქვს ამ minus 1, რადგან ჩვენ არ გვინდა, რომ მოიცავს შუა თავად. ასე n მინუს შუა მინუს 1 გვაძლევს საერთო რაოდენობის ელემენტების უფლება შუა ინდექსი მასივი. 

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

ალტერნატიული სინტაქსი, რომ ახლა, თქვენ დაიწყო, რომ ნახოთ პოინტერები, არის ampersand ღირებულებების შუა პლუს 1. ასე რომ, დაიბრუნოს მისამართი ცენტრიდან პლუს ერთი ელემენტია ღირებულებებს. 

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

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

ახლა, ჩვენ ვერ ორობითი ძებნა მეტი მასივი, რომელიც არის დაუხარისხებელი. ასე რომ, მოდით მიიღოს ამ დახარისხებული out. ახლა შეამჩნია, რომ დალაგების არის ბოლო ორი პარამეტრები int ღირებულებებს, რომელიც array, რომ ჩვენ დახარისხება და int n, რომელიც არის სიგრძეზე მასივი, ჩვენ დახარისხება. ასე რომ, აქ ჩვენ გვინდა განხორციელება დახარისხება ალგორითმი რომ არის o of n კვადრატში. თქვენ შეიძლება აირჩიონ bubble sort, შერჩევა დალაგების ან Insertion დალაგების, ან რამდენიმე სხვა სახის არ გვაქვს ჩანს კლასი. მაგრამ აქ, ჩვენ ვაპირებთ გამოყენება შერჩევის ჯიშია. 

ასე რომ, ჩვენ ვაპირებთ iterate მთელ მასივი. ისე, აქ ჩვენ ვხედავთ, რომ ჩვენ iterating 0 დან n მინუს 1. რატომ არ არის ყველა გზა მდე n? ისე, თუ ჩვენ უკვე დახარისხებული პირველი n მინუს 1 ელემენტები, მაშინ ძალიან ბოლო ელემენტს რა უნდა გადახვიდეთ სწორი ადგილი, ასე დახარისხება მეტი მთელი მასივი. 

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

აქ ჩვენ ვხედავთ, რომ ჩვენ შექმნის მიმდინარე მინიმუმი ღირებულების i-th ინდექსი. ამიტომ პირველ iteration, ჩვენ ვაპირებთ განიხილოს მინიმალური ღირებულება უნდა იყოს დაწყების ჩვენი მასივი. ამის შემდეგ, ჩვენ ვაპირებთ iterate მეტი დარჩენილი მასივი, შემოწმების თუ არსებობს რაიმე ელემენტების ნაკლებია ერთი, რომ ჩვენ ამჟამად გათვალისწინებით მინიმალური. 

ასე რომ აქ, ფასეულობები j პლუს ერთი - რომ ნაკლებია, ვიდრე იმას, რასაც ჩვენ ამჟამად გათვალისწინებით მინიმალური. მაშინ ჩვენ ვაპირებთ განახლება რა ჩვენ მიგვაჩნია, რომ მინიმუმ ინდექსი j პლუს 1. ასე რომ, რომ მთელ მასივი, და შემდეგ ამ for loop, მინიმალური უნდა იყოს მინიმალური ელემენტს საწყისი i-ე პოზიციაზე მასივი. 

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

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