1
00:00:00,000 --> 00:00:02,892
>> [მუსიკის დაკვრა]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: ხაზოვანი
ძებნის ალგორითმი ჩვენ

4
00:00:07,180 --> 00:00:09,840
შეგიძლიათ გამოიყენოთ ელემენტს მასივი.

5
00:00:09,840 --> 00:00:11,990
ალგორითმი გაწვევას
არის ნაბიჯ ნაბიჯ კომპლექტი

6
00:00:11,990 --> 00:00:15,030
ინსტრუქციები დასრულების ამოცანა.

7
00:00:15,030 --> 00:00:17,480
>> ხაზოვანი ძიება
ალგორითმი მუშაობს შემდეგნაირად.

8
00:00:17,480 --> 00:00:22,200
Iterate მასშტაბით მასივი მარცხნიდან
მარჯვენა, ეძებს მითითებული ელემენტს.

9
00:00:22,200 --> 00:00:26,380
>> In pseudocode, რომელიც უფრო
გამოხდილი მობილური ეს წინადადება,

10
00:00:26,380 --> 00:00:29,840
თუ პირველ ელემენტს არის ის, რაც
თქვენ ეძებთ, შეგიძლიათ შეჩერება.

11
00:00:29,840 --> 00:00:33,930
წინააღმდეგ შემთხვევაში, გადატანა მომდევნო ელემენტს და
შენარჩუნება აპირებს მეტი და მეტი, სანამ თქვენთვის

12
00:00:33,930 --> 00:00:36,389
ელემენტი, ან თქვენ არ.

13
00:00:36,389 --> 00:00:38,680
ასე რომ, ჩვენ შეგვიძლია გამოვიყენოთ ხაზოვანი
ძებნის ალგორითმი, მაგალითად,

14
00:00:38,680 --> 00:00:42,330
მოვძებნოთ სამიზნე მნიშვნელობა
ცხრა ამ მასივი.

15
00:00:42,330 --> 00:00:43,870
ისე ჩვენ დაიწყება.

16
00:00:43,870 --> 00:00:45,970
იმ შემთხვევაში, თუ ის, რაც ჩვენ
ეძებს, შეიძლება შეწყდეს.

17
00:00:45,970 --> 00:00:47,890
ეს არ არის, ჩვენ არ ვეძებთ 11.

18
00:00:47,890 --> 00:00:50,220
ასე რომ, წინააღმდეგ შემთხვევაში, გადატანა მომდევნო ელემენტს.

19
00:00:50,220 --> 00:00:51,510
>> ამიტომ, ჩვენ შევხედოთ 23.

20
00:00:51,510 --> 00:00:52,730
23 ის, რასაც ჩვენ ვეძებთ?

21
00:00:52,730 --> 00:00:55,614
ისე არ არის, ასე რომ, ჩვენ გადაადგილება, რათა მომდევნო
ელემენტს, და მეორე ელემენტი,

22
00:00:55,614 --> 00:00:57,780
და ჩვენ შენარჩუნება გადის
ეს პროცესი და მეტი

23
00:00:57,780 --> 00:01:01,030
და მეტი, სანამ ჩვენ მიწაზე
on სიტუაცია მოსწონს ეს.

24
00:01:01,030 --> 00:01:03,910
>> Nine არის ის, რაც ჩვენ ვეძებთ,
და ამ ელემენტს მასივი

25
00:01:03,910 --> 00:01:05,787
ის არის, რომ ის მნიშვნელობა ცხრა.

26
00:01:05,787 --> 00:01:08,120
ამდენად, ჩვენ აღმოვაჩინეთ, რაც ჩვენ
ეძებს, და ჩვენ ვერ შეაჩერებს.

27
00:01:08,120 --> 00:01:11,910
ხაზოვანი ძებნის აქვს
დასრულდა, წარმატებით.

28
00:01:11,910 --> 00:01:15,370
>> მაგრამ რა შეიძლება ითქვას, თუ ჩვენ ვეძებთ
ელემენტს, რომელიც არ არის ჩვენს მასივი.

29
00:01:15,370 --> 00:01:17,040
ამჯამად ხაზოვანი ძებნა კიდევ მუშაობს?

30
00:01:17,040 --> 00:01:17,540
ისე დარწმუნებული ვარ.

31
00:01:17,540 --> 00:01:19,947
ასე რომ, ჩვენ ვიმეორებ ეს პროცესი
დაწყებული პირველ ელემენტს.

32
00:01:19,947 --> 00:01:21,780
იმ შემთხვევაში, თუ ის, რაც ჩვენ
ეძებს, შეიძლება შეწყდეს.

33
00:01:21,780 --> 00:01:22,800
ეს არ არის.

34
00:01:22,800 --> 00:01:25,020
წინააღმდეგ შემთხვევაში, ჩვენ გადაადგილება, რათა მომდევნო ელემენტს.

35
00:01:25,020 --> 00:01:29,050
>> მაგრამ ჩვენ შეგვიძლია შევინარჩუნოთ იმეორებს ამ პროცესში,
შეისწავლა თითოეული ელემენტის თავის მხრივ,

36
00:01:29,050 --> 00:01:31,720
იმ იმედით, რომ ჩვენ ნომერი 50.

37
00:01:31,720 --> 00:01:33,750
მაგრამ ჩვენ არ ვიცით, თუ
ჩვენ აღმოვაჩინეთ ნომერი 50

38
00:01:33,750 --> 00:01:38,290
ან თუ ჩვენ არ, სანამ ჩვენ გადადგა
მეტი თითოეული ელემენტის მასივი.

39
00:01:38,290 --> 00:01:40,440
>> მხოლოდ ერთხელ, ჩვენ გავაკეთეთ
რომ ამუშავება და მოკლე,

40
00:01:40,440 --> 00:01:43,040
შეგვიძლია დავასკვნათ, რომ
50 არ არის მასივი.

41
00:01:43,040 --> 00:01:46,410
ასე რომ, ხაზოვანი ძებნა
ალგორითმი, ასევე ეს ვერ მოხერხდა, თავისთავად.

42
00:01:46,410 --> 00:01:49,181
მაგრამ არა იმ გაგებით, რომ ის
წარუმატებელი აღმოჩნდა კარგის

43
00:01:49,181 --> 00:01:49,930
ჩვენ ვთხოვეთ მას ამის გაკეთება.

44
00:01:49,930 --> 00:01:52,390
>> ეს იყო წარუმატებელი, როგორც
იმდენად, რამდენადაც ეს არ იპოვოს 50,

45
00:01:52,390 --> 00:01:54,070
მაგრამ 50 არ იყო მასივი.

46
00:01:54,070 --> 00:01:57,310
მაგრამ ჩვენ ამომწურავად ჩხრეკა
მეშვეობით თითოეული ელემენტი

47
00:01:57,310 --> 00:02:00,550
და ა.შ., ხოლო ჩვენ ვერ
არაფერი, ხაზოვანი ძებნა მაინც

48
00:02:00,550 --> 00:02:05,230
გაამართლებს თუნდაც
ელემენტი არ არის მასივი.

49
00:02:05,230 --> 00:02:07,507
>> ასე რომ, რა უარეს შემთხვევაში
სცენარი ხაზოვანი ძებნა?

50
00:02:07,507 --> 00:02:09,590
ისე ჩვენ უნდა გაეცნონ
თითოეული ელემენტის,

51
00:02:09,590 --> 00:02:14,590
ან იმიტომ, რომ სამიზნე ელემენტი
ბოლო ელემენტს მასივი,

52
00:02:14,590 --> 00:02:18,510
ან ელემენტს ჩვენ ვეძებთ არ
რეალურად არსებობს მასივი ყველა.

53
00:02:18,510 --> 00:02:19,760
რა არის საუკეთესო სცენარი?

54
00:02:19,760 --> 00:02:22,430
ისე, რომ ჩვენ შეიძლება იპოვოს
ელემენტის დაუყოვნებლივ.

55
00:02:22,430 --> 00:02:24,360
და რამდენი ელემენტები
ჩვენ მაშინ უნდა ვეძებოთ

56
00:02:24,360 --> 00:02:26,859
განთავსებულია საუკეთესო შემთხვევაში,
თუ ჩვენ ვეძებთ მას

57
00:02:26,859 --> 00:02:28,400
და ჩვენ ამას თავიდანვე?

58
00:02:28,400 --> 00:02:29,850
ჩვენ შეგვიძლია შეწყდეს დაუყოვნებლივ.

59
00:02:29,850 --> 00:02:32,984
>> რას გვეუბნება ეს შესახებ
სირთულის ხაზოვანი ძებნა?

60
00:02:32,984 --> 00:02:35,650
ისე, უარეს შემთხვევაში, ჩვენ გვაქვს
შევხედოთ თითოეული ელემენტი.

61
00:02:35,650 --> 00:02:38,930
ასე რომ, იგი ეშვება O of
n, უარეს შემთხვევაში.

62
00:02:38,930 --> 00:02:41,540
>> საუკეთესო შემთხვევაში, ჩვენ კარგად
მოვძებნოთ ელემენტი დაუყოვნებლივ.

63
00:02:41,540 --> 00:02:44,750
ასე რომ ეშვება omega 1.

64
00:02:44,750 --> 00:02:45,780
>> მე Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
ეს არის CS50.

66
00:02:48,020 --> 00:02:49,876