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
>> داگ لوید: بسیار خوب.

4
00:00:06,220 --> 00:00:08,140
بنابراین جستجوی دودویی یک IS
الگوریتم ما می توانید استفاده کنید

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
>> اگر آن را یک مخلوط کردن کامل،
ما نمی توانیم فقط از دست

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
>> پس چه شبه است
این مراحل را برای جستجوی دودویی؟

23
00:00:58,710 --> 00:01:02,310
ما این روند را تکرار تا زمانی که
آرایه یا، به عنوان ما را از طریق ادامه دهید،

24
00:01:02,310 --> 00:01:07,740
آرایه های فرعی، قطعات کوچکتر
آرایه اصلی است، از اندازه 0.

25
00:01:07,740 --> 00:01:10,960
محاسبه نقطه میانی
از آرایه زیر فعلی است.

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
باید بدانید که چگونه بسیاری از
عناصر ما در حال تکرار بیش از،

57
00:02:36,800 --> 00:02:40,010
اما ما در واقع مهم نیست چه
عنصر ما در حال حاضر در به دنبال.

58
00:02:40,010 --> 00:02:41,014
در جستجوی دودویی، کار می کنیم.

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
شماره

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
بنابراین در حال حاضر، آنچه که ما می گویند ما است
باید یک آرایه زیر از اندازه 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
در بدترین حالت، ما تا به حال
به تقسیم کردن یک لیست از عناصر N

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
ورود به سیستم از N بار؛ ما
مجبور به قطع مشکل

195
00:08:40,510 --> 00:08:42,610
در یک و نیم تعداد معینی از بار.

196
00:08:42,610 --> 00:08:45,160
که تعداد دفعاتی ورود n است.

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
در log n است، که قابل ملاحظه ای بهتر
از جستجوی خطی، در بدترین حالت.

208
00:09:11,580 --> 00:09:16,210
در بهترین حالت، باینری
جستجو اجرا می شود در امگا، از مجموع 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
>> من داگ لوید هستم.

213
00:09:27,130 --> 00:09:29,470
این CS 50 است.

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