Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [ხაზოვანი ძებნა]
[პატრიკ შმიდი, ჰარვარდის უნივერსიტეტი]
[This Is CS50.] [CS50.TV]
ძიება არის რაღაც, რომ თქვენ ალბათ უფრო ხშირად ფიქრობთ.
ცხადია, ყველა დროის გახსენით ბრაუზერი
და ძიება ვებ გვერდზე -
ან მოძებნეთ თქვენი მეგობრები, თქვენი საყვარელი სოციალური ქსელის საიტი -
თქვენ ეძებს.
მაგრამ ეს მხოლოდ მცირე ნაწილი ძებნას რომ თქვენ ყოველდღიურად.
როდესაც თქვენ გსურთ იპოვოთ რომ ერთი ლურჯი პერანგი კარადა,
ან რომ სრულყოფილი წითელი blouse ამისთვის შემთხვევა,
თქვენ ეძებს.
როდესაც მიდიხარ მაღაზიაში, რომ თქვენ არასოდეს ყოფილა ადრე,
და თქვენ ვეძებთ ბროკოლი წელს პროდუქციის aisle
თქვენ ეძებს.
რა შეიძლება დაიწყო შეამჩნევთ
ის არის, რომ ეს დამოკიდებულია თუ რას ეძებს
ან როგორ ელემენტი ტარდება, როდესაც თქვენ ეძებს
მას აქვს ეფექტი, თუ როგორ მოძებნოთ.
მაგალითად, თუ თქვენი მაისურები ჰკიდია in კარადა,
თქვენ ალბათ შეუძლია სულაც ის გარეშე გაცილებით ძებნას.
თუ თქვენ თუ ვთქვათ თქვენ გაქვთ ფეხით ქვემოთ aisle
მიიღოს ბროკოლი, თქვენ ალბათ უნდა შევხედოთ ყველა სხვა ბოსტნეული
სანამ თქვენთვის, რომ ბროკოლი.
ხაზოვანი ძებნა არის მაგალითად ერთი ასეთი ძებნას მეთოდი - ან ალგორითმი.
როგორც სახელი გულისხმობს,
ეს მეთოდი ეძებს პუნქტის ხაზოვანი მოდის, ერთი შემდეგ სხვა.
ასე რომ, როდესაც თქვენ ეძებს შედეგი თქვენი საყვარელი საძიებო სისტემა
და წაიკითხოთ ქვემოთ სიაში შედეგი,
თქვენ იყენებთ ხაზოვანი ძებნა.
Okay. მოდით შევხედოთ მაგალითს.
Say გვაქვს სიაში ნომრები - 2, 4, 0, 5, 3, 7, 8, და 1 -
და ჩვენ ვეძებთ ნომერი 0.
ცხადია, თქვენ შეგიძლიათ მისი ხილვა, რომ 0 არის მესამე პოზიცია.
მაგრამ, კომპიუტერული პროგრამა არ არის, რომ გაგვიმართლა.
მას შეუძლია მხოლოდ "ვხედავ" ერთი ნომრის დროს.
ასე რომ, დაწყებული დასაწყისში სიაში,
მას მხოლოდ "ხედავს" 2.
პროგრამის შემდეგ ამოწმებს - არის 2 ტოლი 0?
ცხადია არა. ასე რომ, ეს გრძელდება შემდეგი ნომერი, 4.
Does 4 თანაბარ 0? Nope.
შემდეგი ერთი, 0. Ah! ნულოვანი უდრის 0.
იქ არის ეს! ეს მესამე პოზიცია.
Okay. მოდით შევხედოთ ზოგიერთი pseudocode.
ეს მხოლოდ რამდენიმე ხაზების ხანგრძლივი, მაგრამ მოდით შევხედოთ ერთი ხაზის დროს.
თავიდან, მოდით განვსაზღვროთ ფუნქცია - და ჩვენ ვაპირებთ ეძახით ხაზოვანი ძებნა -
და ეს ხდება ორი არგუმენტები - გასაღები და მასივი.
გასაღები არის, რომ ღირებულება, რომ ჩვენ ვეძებთ,
ისე წინა მაგალითად, რომ იყო ნულოვანი.
Array არის სიაში ნომრები
რომ აქვს ყველა ღირებულებებს, რომ ჩვენ ვაპირებთ ძებნის.
ასე რომ, ის, რაც ჩვენ გვსურს რომ არის ჩვენ გვინდა შევხედოთ -
ყველა პოზიციებზე, ასე იწყება დასაწყისშივე მასივი
სთან ძალიან ბოლომდე მასივი - ასე სიგრძეზე მასივი -
შევხედოთ თითოეული პოზიცია და შეამოწმოს თითოეული.
ასე რომ რა, რომ "ამისთვის" მარყუჟის აკეთებს.
და ყოველ პოზიციას, ჩვენ ვაპირებთ ამბობენ
"ისაა, რომ ღირებულება, რომ მიმდინარე თანამდებობა ტოლია გასაღები, რომ ჩვენ ვეძებთ?"
ასე - წინა მაგალითად ერთხელ, გასაღები იყო 0 -
ამიტომ ჩვენ ვამბობთ "არის მასივი პოზიციაში მე ნულის ტოლია?"
თუ ეს ესეა, ჩვენ ვაპირებთ დაბრუნებას 'i' რადგან ისინი მიმდინარე თანამდებობა ჩვენ დროს.
ასე რომ, წინა მაგალითად,
რომ იყო მესამე პოზიცია.
თუ ჩვენ გავიარეთ მთელი მასივი
და ჩვენ ვერ არაფერი -
ასე ვთქვათ ჩვენ ეძებდნენ ნომერი 500
რომელიც მკაფიოდ არ იყო, რომ მაგალითად -
ჩვენ გვაქვს დასაბრუნებელი რაღაც,
და ჩვენ ვაპირებთ დაბრუნებას -1.
და ჩვენ უბრალოდ დაბრუნების -1 იმიტომ რომ თანამდებობა
რომ არ არსებობს მასივი.
და ა.შ. ეს იმას ნიშნავს, როდესაც თქვენ მას უკან ფუნქცია
ნათქვამია "Hmm, okay. ვფიქრობ მე ვერ არაფერი.
ასე რომ 500 არასდროს ყოფილა იქ. "
ლამაზი რამ შესახებ ხაზოვანი ძებნა არის, რომ
ეს ვიმუშავებთ ნებისმიერ ელემენტების სიები,
მიუხედავად იმისა, თუ როგორ ელემენტი უბრძანა.
არ აქვს მნიშვნელობა, სადაც ბროკოლი არის პროდუქციის aisle.
როგორც თქვენ ფეხით ქვემოთ aisle თავიდან ბოლომდე,
თქვენ ვალდებული საპოვნელად,
თუ ვთქვათ მაღაზიაში არ ამოიწურა ბროკოლი, რა თქმა უნდა.
მაგრამ ყველაზე დიდი ძალა არის ასევე უდიდესი სისუსტე.
Say გაქვთ სიაში ორასი ნომრები
, რომლებიც დალაგებულია 1 დან 200.
თუ თქვენ ვეძებთ ნომერი 198,
თქვენ უნდა მოძებნოთ თითქმის სრული სია ნომრები
სანამ თქვენთვის ერთი თქვენ ეძებთ.
უნდა იყოს უკეთესი გზა!
დანარჩენი დავრწმუნდი, რომ არსებობს.
მაგრამ, რომ თემა მეორე ვიდეო.
აგრეთვე, არ fret!
მხოლოდ იმიტომ, რომ ხაზოვანი ძებნა არ არის საუკეთესო გამოსავალი ყველა სიტუაციაში,
ეს არ ნიშნავს, რომ არ მოდის მოსახერხებელი.
წინააღმდეგ შემთხვევაში, როგორ იპოვოს, რომ ბროკოლი წელს პროდუქციის aisle?
ჩემი სახელი არის პატრიკ შმიდი, და ეს არის CS50.
[CS50.TV]