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

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD ყველა უფლება.

4
00:00:06,220 --> 00:00:08,140
ასე რომ ორობითი ძებნა არის
ალგორითმი ჩვენ შეგვიძლია გამოვიყენოთ

5
00:00:08,140 --> 00:00:10,530
მოვძებნოთ ელემენტი შიგნით მასივი.

6
00:00:10,530 --> 00:00:14,710
განსხვავებით ხაზოვანი ძებნა, ის მოითხოვს
განსაკუთრებული მდგომარეობა უნდა შეხვდნენ წინასწარ,

7
00:00:14,710 --> 00:00:19,020
მაგრამ ეს ასე ბევრად უფრო ეფექტური, თუ
ეს პირობა არის, ფაქტობრივად, შეხვდა.

8
00:00:19,020 --> 00:00:20,470
>> ასე რომ, რა იდეა აქ?

9
00:00:20,470 --> 00:00:21,780
ეს გათიშე და დაიპყროთ.

10
00:00:21,780 --> 00:00:25,100
ჩვენ გვინდა, რომ შეამციროს ზომა
ძებნა ფართობი ნახევარი ყოველ ჯერზე

11
00:00:25,100 --> 00:00:27,240
რათა სამიზნე ნომერი.

12
00:00:27,240 --> 00:00:29,520
ეს არის სადაც, რომ მდგომარეობა
ძალაში პიესა, თუმცა.

13
00:00:29,520 --> 00:00:32,740
ჩვენ შეგვიძლია მხოლოდ ბერკეტი ძალა
მოეღო ნახევარში ელემენტები

14
00:00:32,740 --> 00:00:36,070
გარეშე კი შევხედავთ
მათ, თუ მასივი დალაგებულია.

15
00:00:36,070 --> 00:00:39,200
>> თუ ეს არის სრული mix up,
ჩვენ არ შეგვიძლია უბრალოდ გარეთ მხრივ

16
00:00:39,200 --> 00:00:42,870
გაუქმება ნახევარში ელემენტები, იმიტომ, რომ
ჩვენ არ ვიცით, რა ჩვენ გაქვს.

17
00:00:42,870 --> 00:00:45,624
მაგრამ, თუ მასივი დალაგებულია,
ჩვენ შეგვიძლია ამის გაკეთება, იმიტომ, რომ ჩვენ

18
00:00:45,624 --> 00:00:48,040
ვიცი, რომ ყველაფერი
დარჩა, სადაც ჩვენ გაკეთებული არის

19
00:00:48,040 --> 00:00:50,500
უნდა იყოს დაბალია, ვიდრე
მნიშვნელობა ჩვენ ამჟამად.

20
00:00:50,500 --> 00:00:52,300
და ყველაფერი
უფლება, სადაც ჩვენ ვართ

21
00:00:52,300 --> 00:00:55,040
უნდა იყოს მეტი ღირებულების
ჩვენ გაკეთებული ეძებს.

22
00:00:55,040 --> 00:00:58,710
>> რა არის pseudocode
ნაბიჯები ორობითი ძებნა?

23
00:00:58,710 --> 00:01:02,310
ჩვენ ვიმეორებ ეს პროცესი მანამ, სანამ
array ან, როგორც ჩვენ გაგრძელება მეშვეობით,

24
00:01:02,310 --> 00:01:07,740
ქვე მასივები, პატარა ცალი
ორიგინალური მასივი, ზომა 0.

25
00:01:07,740 --> 00:01:10,960
გამოთვალოთ შუაში
მიმდინარე sub მასივი.

26
00:01:10,960 --> 00:01:14,460
>> თუ ღირებულება თქვენ ვეძებთ არის
ამ ელემენტს მასივი, შეწყვიტოს.

27
00:01:14,460 --> 00:01:15,030
თქვენ ი.

28
00:01:15,030 --> 00:01:16,550
სწორედ დიდი.

29
00:01:16,550 --> 00:01:19,610
წინააღმდეგ შემთხვევაში, თუ სამიზნე
ნაკლებია, ვიდრე რა არის ახლო,

30
00:01:19,610 --> 00:01:23,430
ასე რომ, თუ ღირებულების ჩვენ ვეძებთ
არის დაბალია, ვიდრე რასაც ჩვენ ვხედავთ,

31
00:01:23,430 --> 00:01:26,780
ვიმეორებ ეს პროცესი კიდევ ერთხელ, მაგრამ
შეცვლა ბოლომდე წერტილი, ნაცვლად

32
00:01:26,780 --> 00:01:29,300
მიმდინარეობს ორიგინალური
შეავსოთ სრული მასივი,

33
00:01:29,300 --> 00:01:34,110
უნდა იყოს მხოლოდ, რომ მარცხნივ
სადაც ჩვენ უბრალოდ ჩანდა.

34
00:01:34,110 --> 00:01:38,940
>> ჩვენ ვიცოდით, რომ შუა იყო ძალიან მაღალი,
ან სამიზნე ნაკლები იყო შუა,

35
00:01:38,940 --> 00:01:42,210
და ამიტომ უნდა არსებობდეს, თუ იგი
არსებობს ყველა მასივი,

36
00:01:42,210 --> 00:01:44,660
სადღაც მარცხნივ შუაში.

37
00:01:44,660 --> 00:01:48,120
ასე რომ, ჩვენ ვაყენებთ მასივი
განთავსების უბრალოდ, რომ მარცხნივ

38
00:01:48,120 --> 00:01:51,145
შუაში, როგორც ახალი ბოლომდე წერტილი.

39
00:01:51,145 --> 00:01:53,770
პირიქით, თუ სამიზნე
მეტი რა არის ახლო,

40
00:01:53,770 --> 00:01:55,750
ჩვენ ზუსტად იგივე
პროცესი, არამედ ჩვენ

41
00:01:55,750 --> 00:01:59,520
შეცვლა დაწყების წერტილი უნდა იყოს
მხოლოდ მარჯვნივ შუაში

42
00:01:59,520 --> 00:02:00,680
ჩვენ უბრალოდ გათვლილი.

43
00:02:00,680 --> 00:02:03,220
და მაშინ, ჩვენ დაიწყოს პროცესი კიდევ ერთხელ.

44
00:02:03,220 --> 00:02:05,220
>> მოდით ვიზუალურად, OK?

45
00:02:05,220 --> 00:02:08,620
ასე რომ, ბევრი რამ ხდება და აქ,
მაგრამ აქ არის მასივი 15 ელემენტები.

46
00:02:08,620 --> 00:02:11,400
და ჩვენ ვაპირებთ, უნდა შენახვა სიმღერა
ბევრი პერსონალი ამ დროს.

47
00:02:11,400 --> 00:02:13,870
ასე რომ, ხაზოვანი ძებნა, ჩვენ
მხოლოდ ზრუნვა სამიზნე.

48
00:02:13,870 --> 00:02:15,869
მაგრამ ამ დროს ჩვენ გვინდა
აინტერესებს სად ვართ ჩვენ

49
00:02:15,869 --> 00:02:18,480
იწყება გამოიყურებოდეს, სადაც
ვართ ჩვენ შეჩერების ეძებს,

50
00:02:18,480 --> 00:02:21,876
და რა არის შუაში
მიმდინარე მასივი.

51
00:02:21,876 --> 00:02:23,250
ასე რომ, აქ ჩვენ წავიდეთ ერთად ორობითი ძებნა.

52
00:02:23,250 --> 00:02:25,290
ჩვენ საკმაოდ ბევრი კარგი, არა?

53
00:02:25,290 --> 00:02:28,650
მე უბრალოდ აპირებს ჩასახშობად
ქვემოთ აქ კომპლექტი მაჩვენებლები.

54
00:02:28,650 --> 00:02:32,430
ეს არის, ძირითადად, მხოლოდ, რა ელემენტს
მასივი ჩვენ ვსაუბრობთ.

55
00:02:32,430 --> 00:02:34,500
ხაზოვანი ძებნა, ჩვენ
მაინტერესებს, ვინაიდან ჩვენ

56
00:02:34,500 --> 00:02:36,800
უნდა ვიცოდეთ, რამდენი
ელემენტები ჩვენ iterating მეტი,

57
00:02:36,800 --> 00:02:40,010
მაგრამ ჩვენ რეალურად არ აინტერესებს, თუ რა
ელემენტს ჩვენ გაკეთებული ეძებს.

58
00:02:40,010 --> 00:02:41,014
In ორობითი ძებნა, რასაც ჩვენ ვაკეთებთ.

59
00:02:41,014 --> 00:02:42,930
ასე რომ, ეს მხოლოდ
იქ, როგორც პატარა სახელმძღვანელო.

60
00:02:42,930 --> 00:02:44,910
>> ასე რომ, ჩვენ შეგვიძლია დავიწყოთ, არა?

61
00:02:44,910 --> 00:02:46,240
ისე, არ საკმაოდ.

62
00:02:46,240 --> 00:02:48,160
მახსოვს რა ვთქვი
ორობითი ძებნა?

63
00:02:48,160 --> 00:02:50,955
ჩვენ არ შეგვიძლია ამის გაკეთება შესახებ
დაუხარისხებელი მასივი ანდა,

64
00:02:50,955 --> 00:02:55,820
ჩვენ არ ვართ იმისა, რომ
გარკვეული ელემენტები და ღირებულებები არ არის

65
00:02:55,820 --> 00:02:57,650
მიმდინარეობს შემთხვევით
უგულვებელყოფილია, როდესაც ჩვენ მხოლოდ

66
00:02:57,650 --> 00:02:59,920
უგულებელყოფს ნახევარში მასივი.

67
00:02:59,920 --> 00:03:02,574
>> ასე ნაბიჯი ერთი ორობითი ძებნა
არის, თქვენ უნდა აქვს დახარისხებული მასივი.

68
00:03:02,574 --> 00:03:05,240
თქვენ შეგიძლიათ გამოიყენოთ ნებისმიერი დახარისხება
ალგორითმები ჩვენ ვისაუბრეთ

69
00:03:05,240 --> 00:03:06,700
მისაღებად თქვენ ამ თანამდებობაზე.

70
00:03:06,700 --> 00:03:10,370
ასე რომ, ახლა ჩვენ პოზიცია, სადაც
ჩვენ შეუძლია შეასრულოს ორობითი ძებნა.

71
00:03:10,370 --> 00:03:12,560
>> მოდით გავიმეოროთ პროცესში
ეტაპობრივად და შენარჩუნება

72
00:03:12,560 --> 00:03:14,830
სიმღერა, თუ რა ხდება, როგორც ჩვენ მივდივართ.

73
00:03:14,830 --> 00:03:17,980
ასე რომ, პირველ რიგში, ჩვენ უნდა გავაკეთოთ არის გამოთვლა
შუაში მიმდინარე მასივი.

74
00:03:17,980 --> 00:03:20,620
ისე, ჩვენ ვიტყვით, ჩვენ, პირველ
ყველა, ეძებს ღირებულება 19.

75
00:03:20,620 --> 00:03:22,290
ჩვენ ვცდილობთ, რომ იპოვოს ნომერი 19.

76
00:03:22,290 --> 00:03:25,380
პირველი ელემენტი ამ
მასივი მდებარეობს ინდექსი ნულოვანი,

77
00:03:25,380 --> 00:03:28,880
და ბოლო ელემენტს ამ
მასივი მდებარეობს ინდექსი 14.

78
00:03:28,880 --> 00:03:31,430
ასე რომ, ჩვენ მოვუწოდებთ მათ, დაწყების და დასრულების.

79
00:03:31,430 --> 00:03:35,387
>> ასე რომ, ჩვენ გამოვთვალოთ შუაში მიერ
დასძინა 0 + 14 გაყოფილი 2;

80
00:03:35,387 --> 00:03:36,720
საკმაოდ მარტივია შუაში.

81
00:03:36,720 --> 00:03:40,190
და შეიძლება ითქვას, რომ
შუაში არის 7.

82
00:03:40,190 --> 00:03:43,370
ასე რომ, 15, რასაც ჩვენ ვეძებთ?

83
00:03:43,370 --> 00:03:43,940
არა, ეს ასე არ არის.

84
00:03:43,940 --> 00:03:45,270
ჩვენ ვეძებთ 19.

85
00:03:45,270 --> 00:03:49,400
მაგრამ ჩვენ ვიცით, რომ 19 არის უფრო მეტი
ვიდრე ის, რაც ჩვენ აღმოვაჩინეთ შუა.

86
00:03:49,400 --> 00:03:52,470
>> ასე რომ, რა შეგვიძლია გავაკეთოთ არის
შეცვლა დაწყების წერტილი

87
00:03:52,470 --> 00:03:57,280
უნდა იყოს მხოლოდ მარჯვნივ
შუაში, და ვიმეორებ პროცესში კიდევ ერთხელ.

88
00:03:57,280 --> 00:04:01,690
და როდესაც ჩვენ გავაკეთებთ, რომ ჩვენ ახლა აცხადებენ, რომ
ახალი დაწყების წერტილი არის მასივი ადგილმდებარეობა 8.

89
00:04:01,690 --> 00:04:07,220
რა ჩვენ ეფექტურად გაკეთდეს არის
იგნორირებულია იმისათვის, რომ მარცხნივ 15.

90
00:04:07,220 --> 00:04:09,570
ჩვენ აღმოფხვრილი ნახევარი
პრობლემა, და ახლა,

91
00:04:09,570 --> 00:04:13,510
ნაცვლად, რომელმაც უნდა ვეძებოთ
15-ზე მეტი ელემენტები ჩვენს მასივი,

92
00:04:13,510 --> 00:04:15,610
ჩვენ მხოლოდ უნდა ვეძებოთ 7.

93
00:04:15,610 --> 00:04:17,706
ასე რომ, 8 არის ახალი ამოსავალი წერტილი.

94
00:04:17,706 --> 00:04:19,600
14 ჯერ კიდევ ბოლომდე წერტილი.

95
00:04:19,600 --> 00:04:21,430
>> და ახლა, ჩვენ წავიდეთ ამ ერთხელ.

96
00:04:21,430 --> 00:04:22,810
ჩვენ გამოვთვალოთ ახალი შუაში.

97
00:04:22,810 --> 00:04:27,130
8 + 14 22, გაყოფილი 2-11.

98
00:04:27,130 --> 00:04:28,660
ეს არის ის, რაც ჩვენ ვეძებთ?

99
00:04:28,660 --> 00:04:30,110
არა, ეს ასე არ არის.

100
00:04:30,110 --> 00:04:32,930
ჩვენ ვეძებთ ღირებულება, რომელიც არის
ნაკლებია, ვიდრე ის, რაც ჩვენ უბრალოდ ი.

101
00:04:32,930 --> 00:04:34,721
ასე რომ, ჩვენ ვაპირებთ გავიმეორო
პროცესი კიდევ ერთხელ.

102
00:04:34,721 --> 00:04:38,280
ჩვენ ვაპირებთ, რომ შეიცვალოს ბოლოს წერტილი
იყოს მხოლოდ, რომ მარცხნივ შუაში.

103
00:04:38,280 --> 00:04:41,800
ასე რომ, ახალი ბოლომდე წერტილი ხდება 10.

104
00:04:41,800 --> 00:04:44,780
და ახლა, რომ ეს არის მხოლოდ ნაწილი
მასივი ჩვენ უნდა დასალაგებლად მეშვეობით.

105
00:04:44,780 --> 00:04:48,460
ასე რომ, ჩვენ უკვე აღმოფხვრილი
12 15 ელემენტებს.

106
00:04:48,460 --> 00:04:51,550
ჩვენ ვიცით, რომ თუ 19
არსებობს მასივი, ის

107
00:04:51,550 --> 00:04:57,210
უნდა არსებობდეს სადღაც შორის ელემენტი
ნომერი 8 და ელემენტს ნომერი 10.

108
00:04:57,210 --> 00:04:59,400
>> ასე რომ, ჩვენ გამოვთვალოთ ახალი შუაში კვლავ.

109
00:04:59,400 --> 00:05:02,900
8 + 10 18, გაყოფილი 2-9.

110
00:05:02,900 --> 00:05:05,074
და ამ შემთხვევაში, გამოიყურება,
სამიზნე არის შუა.

111
00:05:05,074 --> 00:05:06,740
ჩვენ აღმოვაჩინეთ, რაც ჩვენ ვეძებთ.

112
00:05:06,740 --> 00:05:07,780
ჩვენ შეგვიძლია შეწყვიტოს.

113
00:05:07,780 --> 00:05:10,561
ჩვენ წარმატებით დასრულდა
ორობითი ძებნა.

114
00:05:10,561 --> 00:05:11,060
ყველა უფლება.

115
00:05:11,060 --> 00:05:13,930
ასე რომ, ჩვენ ვიცით, რომ ეს ალგორითმი
მუშაობს თუ სამიზნე

116
00:05:13,930 --> 00:05:16,070
სადღაც შიგნით მასივი.

117
00:05:16,070 --> 00:05:19,060
ნიშნავს თუ არა ეს ალგორითმი მუშაობს თუ
სამიზნე არ არის მასივი?

118
00:05:19,060 --> 00:05:20,810
მოდით, დავიწყოთ ეს
კიდევ ერთხელ, და ამ დროს,

119
00:05:20,810 --> 00:05:23,380
მოდით შევხედოთ ელემენტს
16, რომელიც ვიზუალურად, ჩვენ ვხედავთ,

120
00:05:23,380 --> 00:05:25,620
არ არსებობს სადმე მასივი.

121
00:05:25,620 --> 00:05:27,110
>> საწყის ეტაპზე ისევ 0.

122
00:05:27,110 --> 00:05:28,590
ბოლოს წერტილი ისევ 14.

123
00:05:28,590 --> 00:05:32,490
ესენი არიან მაჩვენებლების პირველი და
ბოლო ელემენტების სრული მასივი.

124
00:05:32,490 --> 00:05:36,057
და ჩვენ გავლა პროცესი ჩვენ უბრალოდ
გაიარა ერთხელ, ცდილობს იპოვოს 16

125
00:05:36,057 --> 00:05:39,140
მიუხედავად იმისა, რომ ვიზუალურად, ჩვენ შეგვიძლია უკვე
გითხრათ, რომ ის არ აპირებს იყოს იქ.

126
00:05:39,140 --> 00:05:43,450
ჩვენ უბრალოდ გვინდა დავრწმუნდეთ, რომ ეს ალგორითმი
რომელიც, ფაქტობრივად, ჯერ კიდევ მუშაობენ რამდენიმე გზა

127
00:05:43,450 --> 00:05:46,310
და არა მხოლოდ დაგვტოვებთ
დავრჩებოდით უსასრულო ციკლი.

128
00:05:46,310 --> 00:05:48,190
>> რა არის ნაბიჯი პირველი?

129
00:05:48,190 --> 00:05:50,230
გამოთვალოთ შუაში
მიმდინარე მასივი.

130
00:05:50,230 --> 00:05:52,790
რა არის შუაში
მიმდინარე მასივი?

131
00:05:52,790 --> 00:05:54,410
ისე, ეს 7, არა?

132
00:05:54,410 --> 00:05:57,560
14 + 0 იყოფა 2 7.

133
00:05:57,560 --> 00:05:59,280
15 ის, რასაც ჩვენ ვეძებთ?

134
00:05:59,280 --> 00:05:59,780
No.

135
00:05:59,780 --> 00:06:02,930
ეს არის საკმაოდ ახლოს, მაგრამ ჩვენ ვეძებთ
დიდი მნიშვნელობა ოდნავ დიდია, ვიდრე ეს.

136
00:06:02,930 --> 00:06:06,310
>> ჩვენ ვიცით, რომ ის აპირებს
იყოს არსად მარცხნივ 15.

137
00:06:06,310 --> 00:06:08,540
სამიზნე არის უფრო მეტი, ვიდრე
რა არის შუაში.

138
00:06:08,540 --> 00:06:12,450
ასე რომ, ჩვენ დავსახეთ ახალი დაწყების წერტილი
იყოს მხოლოდ მარჯვნივ ცენტრიდან.

139
00:06:12,450 --> 00:06:16,130
შუაში არის გაკეთებული 7, ამიტომ
მოდით ვთქვათ, რომ ახალი დაწყების წერტილი 8.

140
00:06:16,130 --> 00:06:18,130
და რა ჩვენ ეფექტურად
გაკეთდეს ერთხელ იგნორირებულია

141
00:06:18,130 --> 00:06:21,150
მთელი მარცხენა ნახევარში მასივი.

142
00:06:21,150 --> 00:06:23,750
>> ახლა, ჩვენ ვიმეორებთ
დამუშავებას კიდევ ერთხელ.

143
00:06:23,750 --> 00:06:24,910
გამოთვალეთ ახალი შუაში.

144
00:06:24,910 --> 00:06:29,350
8 + 14 22, გაყოფილი 2-11.

145
00:06:29,350 --> 00:06:31,060
23 ის, რასაც ჩვენ ვეძებთ?

146
00:06:31,060 --> 00:06:31,870
სამწუხაროდ, არ არსებობს.

147
00:06:31,870 --> 00:06:34,930
ჩვენ ვეძებთ მნიშვნელობა
რომ ნაკლებია 23.

148
00:06:34,930 --> 00:06:37,850
ასე რომ, ამ შემთხვევაში, ჩვენ ვაპირებთ
შეცვალოს ბოლომდე წერტილი უნდა იყოს მხოლოდ

149
00:06:37,850 --> 00:06:40,035
მარცხნივ მიმდინარე შუაში.

150
00:06:40,035 --> 00:06:43,440
მიმდინარე შუაში არის 11, და
ასე რომ, ჩვენ დავსახეთ ახალი ბოლომდე წერტილი

151
00:06:43,440 --> 00:06:46,980
მომდევნო ჯერზე ჩვენ
ეს პროცესი 10.

152
00:06:46,980 --> 00:06:48,660
>> კიდევ ერთხელ, ჩვენ გავლა პროცესი კიდევ ერთხელ.

153
00:06:48,660 --> 00:06:49,640
გამოთვალეთ შუაში.

154
00:06:49,640 --> 00:06:53,100
8 + 10 იყოფა 2 9.

155
00:06:53,100 --> 00:06:54,750
19 ის, რასაც ჩვენ ვეძებთ?

156
00:06:54,750 --> 00:06:55,500
სამწუხაროდ, არ არსებობს.

157
00:06:55,500 --> 00:06:58,050
ჩვენ ჯერ კიდევ ეძებს
რიგი ნაკლებია.

158
00:06:58,050 --> 00:07:02,060
ასე რომ, ჩვენ შეიცვლება ბოლომდე წერტილი ამ დროს
უნდა იყოს მხოლოდ, რომ მარცხნივ შუაში.

159
00:07:02,060 --> 00:07:05,532
შუაში არის გაკეთებული 9,
ასე ბოლომდე წერტილი იქნება 8.

160
00:07:05,532 --> 00:07:07,920
და ახლა, ჩვენ უბრალოდ ეძებს
განთავსებულია ერთ ელემენტს მასივი.

161
00:07:07,920 --> 00:07:10,250
>> რა არის შუაში ამ მასივი?

162
00:07:10,250 --> 00:07:13,459
ისე, ეს იწყება 8, ეს
მთავრდება 8, შუაში არის 8.

163
00:07:13,459 --> 00:07:14,750
ის არის, რომ ის, რაც ჩვენ ვეძებთ?

164
00:07:14,750 --> 00:07:16,339
ნუთუ ჩვენ ვეძებთ 17?

165
00:07:16,339 --> 00:07:17,380
არა, ჩვენ ვეძებთ 16.

166
00:07:17,380 --> 00:07:20,160
ასე რომ, თუ ის არსებობს მასივი,
ის უნდა არსებობდეს სადღაც

167
00:07:20,160 --> 00:07:21,935
მარცხნივ, სადაც ამჟამად არიან.

168
00:07:21,935 --> 00:07:23,060
ასე რომ, რასაც ჩვენ ვაპირებთ, რომ გავაკეთოთ?

169
00:07:23,060 --> 00:07:26,610
ისე, ჩვენ ვაყენებთ ბოლომდე წერტილი უნდა იყოს მხოლოდ
მარცხნივ მიმდინარე შუაში.

170
00:07:26,610 --> 00:07:29,055
ასე რომ, ჩვენ შეიცვლება ბოლომდე წერტილი 7.

171
00:07:29,055 --> 00:07:32,120
ნუ ხედავთ რა უბრალოდ
აქ მოხდა, თუმცა?

172
00:07:32,120 --> 00:07:33,370
შეხედეთ აქ ახლა.

173
00:07:33,370 --> 00:07:35,970
>> დაწყება არის უფრო მეტი, ვიდრე ბოლომდე.

174
00:07:35,970 --> 00:07:39,620
ეფექტურად, ორი მთავრდება
ჩვენი მასივი გადაკვეთა,

175
00:07:39,620 --> 00:07:42,252
და დაწყების წერტილი არის
მას შემდეგ, რაც ბოლომდე წერტილი.

176
00:07:42,252 --> 00:07:43,960
ისე, რომ არ
არანაირი აზრი, არა?

177
00:07:43,960 --> 00:07:47,960
ახლა, რა შეგვიძლია ვთქვათ, რომ ჩვენ
აქვს sub მასივი ზომა 0.

178
00:07:47,960 --> 00:07:50,110
და კიდევ ჩვენ მიღებული
ამ ეტაპზე, ჩვენ ახლა

179
00:07:50,110 --> 00:07:53,940
გარანტიას გაძლევთ, რომ ელემენტს 16
არ არსებობს მასივი,

180
00:07:53,940 --> 00:07:56,280
იმის გამო, რომ საწყის ეტაპზე
და ბოლოს წერტილი გადმოკვეთა.

181
00:07:56,280 --> 00:07:58,340
ასე რომ, ეს არ არის.

182
00:07:58,340 --> 00:08:01,340
ახლა, რომ ეს არის ოდნავ
განსხვავებული, ვიდრე დაწყების წერტილი და ბოლოს

183
00:08:01,340 --> 00:08:02,900
აღვნიშნო, რომ იგივე.

184
00:08:02,900 --> 00:08:05,030
თუ ჩვენ უკვე ეძებს
17, ეს იქნებოდა

185
00:08:05,030 --> 00:08:08,870
უკვე მასივი, და დაწყების წერტილი
და ბოლოს წერტილი, რომ ბოლო მცდელობაა

186
00:08:08,870 --> 00:08:11,820
ადრე იმ რაოდენობა გადმოკვეთა,
ჩვენ არ გამოვლინდა 17 არსებობს.

187
00:08:11,820 --> 00:08:15,510
ეს მხოლოდ მაშინ, როდესაც ისინი გადაკვეთენ, რომ ჩვენ შეგვიძლია
გარანტიას გაძლევთ, რომ ელემენტს არ

188
00:08:15,510 --> 00:08:17,180
არსებობს მასივი.

189
00:08:17,180 --> 00:08:20,260
>> ასე რომ, მოდით ბევრი ნაკლები
ნაბიჯები, ვიდრე სწორხაზოვანი ძებნა.

190
00:08:20,260 --> 00:08:23,250
უარეს შემთხვევაში, ჩვენ გვქონდა
გაყოფილი სია ო ელემენტები

191
00:08:23,250 --> 00:08:27,770
არაერთხელ ნახევარი მოვძებნოთ სამიზნე,
ან იმიტომ, რომ სამიზნე ელემენტი

192
00:08:27,770 --> 00:08:33,110
იქნება სადღაც ბოლო
დაყოფა, ან ის არ არსებობს.

193
00:08:33,110 --> 00:08:37,830
ასე რომ, უარეს შემთხვევაში, ჩვენ უნდა
გაყოფილი მასივი იცით?

194
00:08:37,830 --> 00:08:40,510
შესვლა ო ჯერ; ჩვენ
უნდა გაჭრა პრობლემა

195
00:08:40,510 --> 00:08:42,610
ნახევარი გარკვეული რაოდენობის ჯერ.

196
00:08:42,610 --> 00:08:45,160
ეს ნომერი ჯერ ჟურნალი ო.

197
00:08:45,160 --> 00:08:46,510
>> რა არის საუკეთესო სცენარი?

198
00:08:46,510 --> 00:08:48,899
ისე, ჩვენ პირველად
გამოთვალოთ შუაში,

199
00:08:48,899 --> 00:08:50,190
ჩვენ იპოვოს ის, რაც ჩვენ ვეძებთ.

200
00:08:50,190 --> 00:08:52,150
ყველა წინა
მაგალითები ორობითი ძებნა

201
00:08:52,150 --> 00:08:55,489
ჩვენ უბრალოდ წავიდა, თუ ჩვენ გვქონდა
უკვე ეძებს ელემენტს 15

202
00:08:55,489 --> 00:08:57,030
ჩვენ არ აღმოაჩინა, რომ დაუყოვნებლივ.

203
00:08:57,030 --> 00:08:58,321
ეს იყო თავიდანვე.

204
00:08:58,321 --> 00:09:01,200
ეს იყო შუაში
პირველი მცდელობა გაყოფილი

205
00:09:01,200 --> 00:09:03,950
სამმართველოს ორობითი ძებნა.

206
00:09:03,950 --> 00:09:06,350
>> ასე რომ, უარეს
იმ შემთხვევაში, ორობითი ძებნა გადის

207
00:09:06,350 --> 00:09:11,580
ჟურნალის n, რომელიც არსებითად უკეთესი
ვიდრე სწორხაზოვანი ძებნა, უარეს შემთხვევაში.

208
00:09:11,580 --> 00:09:16,210
საუკეთესო შემთხვევაში, ორობითი
ძიება ეშვება omega 1.

209
00:09:16,210 --> 00:09:18,990
ასე რომ ორობითი ძებნა ბევრი
უკეთესად ხაზოვანი ძებნა,

210
00:09:18,990 --> 00:09:23,270
მაგრამ თქვენ უნდა გაუმკლავდეთ პროცესში
დახარისხება თქვენი მასივი სანამ შეუძლია

211
00:09:23,270 --> 00:09:26,140
ბერკეტი ძალა ორობითი ძებნა.

212
00:09:26,140 --> 00:09:27,130
>> მე Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
ეს არის CS 50.

214
00:09:29,470 --> 00:09:31,070