1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: سلام، من راب هستم.

3
00:00:15,010 --> 00:00:16,790
چگونه ما از یک جستجوی دودویی؟

4
00:00:16,790 --> 00:00:18,770
بیایید پیدا کردن.

5
00:00:18,770 --> 00:00:23,400
بنابراین، توجه داشته باشید که این جستجو ما در حال رفتن
برای پیاده سازی به صورت بازگشتی.

6
00:00:23,400 --> 00:00:27,470
شما همچنین می توانید جستجوی دودویی پیاده سازی
تکرار، بنابراین اگر شما کار را انجام دادیم،

7
00:00:27,470 --> 00:00:29,280
که کاملا خوب است.

8
00:00:29,280 --> 00:00:32,820
>> در حال حاضر برای اولین بار، اجازه دهید به یاد داشته باشید آنچه را که
پارامتر به جستجو به منظور باشد.

9
00:00:32,820 --> 00:00:36,120
در اینجا، ما ارزش بین المللی است که ببینید
تصور می شود ارزش به کاربر است

10
00:00:36,120 --> 00:00:37,320
جستجو برای.

11
00:00:37,320 --> 00:00:40,800
ما می بینیم آرایه مقادیر بین المللی، که
آرایه است که در آن ما است

12
00:00:40,800 --> 00:00:42,520
جستجو برای ارزش.

13
00:00:42,520 --> 00:00:45,602
و ما می بینیم اعضای هیات n که
طول آرایه است.

14
00:00:45,602 --> 00:00:47,410
>> در حال حاضر، اولین چیزی که برای اولین بار.

15
00:00:47,410 --> 00:00:51,350
ما چک کنید اگر n برابر 0 و در
که در این صورت ما بازگشت کاذب.

16
00:00:51,350 --> 00:00:54,770
که فقط گفت: اگر ما خالی
آرایه، ارزش است که به وضوح در نمی

17
00:00:54,770 --> 00:00:57,860
آرایه خالی، بنابراین ما می توانیم نادرست بازگشت.

18
00:00:57,860 --> 00:01:01,250
>> در حال حاضر، ما در واقع می خواهیم انجام دهیم دودویی
جستجو بخشی از جستجوی دودویی.

19
00:01:01,250 --> 00:01:04,780
بنابراین، ما می خواهیم برای پیدا کردن وسط
عنصر این آرایه.

20
00:01:04,780 --> 00:01:09,130
در اینجا، ما می گویند وسط برابر است با N تقسیم
2، از عنصر وسط است

21
00:01:09,130 --> 00:01:12,240
رفتن به طول
آرایه ما تقسیم بر 2.

22
00:01:12,240 --> 00:01:15,040
در حال حاضر ما در حال رفتن به چک کنید اگر
عنصر وسط برابر است با ارزش ما

23
00:01:15,040 --> 00:01:16,160
جستجو برای.

24
00:01:16,160 --> 00:01:21,030
بنابراین اگر ارزش متوسط ​​برابر است با ارزش، ما
می تواند به راست از ما در بر داشت

25
00:01:21,030 --> 00:01:22,810
مقدار در آرایه است.

26
00:01:22,810 --> 00:01:26,380
>> اما اگر که شد درست نیست، در حال حاضر
ما نیاز به انجام بازگشتی

27
00:01:26,380 --> 00:01:27,840
مرحله از جستجوی دودویی.

28
00:01:27,840 --> 00:01:30,450
ما نیاز به جستجو یا به
سمت چپ آرایه یا به

29
00:01:30,450 --> 00:01:32,320
وسط آرایه.

30
00:01:32,320 --> 00:01:39,280
بنابراین در اینجا، ما می گویند اگر ارزش ها در وسط است
کمتر از ارزش، که بدان معنی است که مقدار

31
00:01:39,280 --> 00:01:41,350
بیشتر از متوسط ​​بود
از آرایه.

32
00:01:41,350 --> 00:01:45,790
بنابراین مقدار باید در سمت راست باشد
عنصری است که ما فقط نگاه کرد.

33
00:01:45,790 --> 00:01:48,090
>> بنابراین در اینجا، ما قصد داریم به
جستجو به صورت بازگشتی.

34
00:01:48,090 --> 00:01:50,320
و ما در آنچه ما در حال عبور نگاه
این در یک ثانیه.

35
00:01:50,320 --> 00:01:53,440
اما ما قصد داریم برای جستجو به
راست عنصر وسط.

36
00:01:53,440 --> 00:01:57,710
و در مورد دیگر، که بدان معنی است که
ارزش کمتر از وسط بود

37
00:01:57,710 --> 00:02:00,660
آرایه و غیره ما در حال رفتن
برای جستجو به سمت چپ.

38
00:02:00,660 --> 00:02:03,520
در حال حاضر، سمت چپ است برای رفتن به
کمی ساده تر نگاه کنید.

39
00:02:03,520 --> 00:02:07,770
بنابراین، ما در اینجا ببینید که ما به صورت بازگشتی است
تماس جست و جو که در آن برای اولین بار

40
00:02:07,770 --> 00:02:10,120
بحث، دوباره، ارزش
ما به دنبال بیش از.

41
00:02:10,120 --> 00:02:14,970
آرگومان دوم است برای رفتن به
مجموعه ای که ما بیش از جستجوی شد.

42
00:02:14,970 --> 00:02:17,090
و آخرین عنصر در حال حاضر متوسط ​​است.

43
00:02:17,090 --> 00:02:21,650
به یاد داشته باشید آخرین پارامتر از نوع int ما
نفر، به طوری که طول آرایه ما است.

44
00:02:21,650 --> 00:02:25,310
>> در تماس بازگشتی را برای جستجو، ما هستیم
در حال حاضر گفت که طول

45
00:02:25,310 --> 00:02:27,230
مجموعه ای متوسط ​​است.

46
00:02:27,230 --> 00:02:32,900
بنابراین، اگر آرایه ما از اندازه 20 و ما بود
جستجو در صفحه 10، از متوسط ​​است

47
00:02:32,900 --> 00:02:36,930
20 تقسیم بر 2، که به معنی ما
پس از 10 عنوان جدید

48
00:02:36,930 --> 00:02:38,300
طول آرایه است.

49
00:02:38,300 --> 00:02:41,910
به یاد داشته باشید که زمانی که شما یک آرایه
طول 10، این بدان معناست که معتبر

50
00:02:41,910 --> 00:02:45,450
عناصر در شاخص های 0 تا 9 می باشد.

51
00:02:45,450 --> 00:02:50,120
بنابراین این دقیقا همان چیزی است که ما به خواهید
مشخص به روز شده در آرایه ما - سمت چپ

52
00:02:50,120 --> 00:02:53,010
مجموعه ای از عنصر وسط.

53
00:02:53,010 --> 00:02:55,710
>> بنابراین، به دنبال حق است
کمی مشکل تر است.

54
00:02:55,710 --> 00:03:00,170
در حال حاضر برای اولین بار، اجازه دهید طول در نظر
از آرایه به سمت راست

55
00:03:00,170 --> 00:03:01,240
عنصر وسط.

56
00:03:01,240 --> 00:03:08,390
بنابراین، اگر آرایه ما از نفر اندازه بود، پس از آن
مجموعه ای جدید از سایز n منفی می شود

57
00:03:08,390 --> 00:03:10,140
منهای متوسط ​​1.

58
00:03:10,140 --> 00:03:12,530
بنابراین، اجازه دهید از n منهای وسط فکر می کنم.

59
00:03:12,530 --> 00:03:18,710
>> باز هم، اگر آرایه ای از اندازه 20 و
ما 2 تقسیم به دریافت وسط،

60
00:03:18,710 --> 00:03:23,540
تا وسط 10، و سپس N منهای متوسط ​​است
به ما 10 تا 10 را

61
00:03:23,540 --> 00:03:25,330
عناصر در سمت راست وسط.

62
00:03:25,330 --> 00:03:27,780
اما ما همچنین این منفی دارند
1، از آنجایی که ما نمی خواهند

63
00:03:27,780 --> 00:03:29,700
عبارتند از وسط خود را.

64
00:03:29,700 --> 00:03:34,190
بنابراین N منهای وسط منهای 1 به ما می دهد
تعداد کل عناصر را به سمت راست

65
00:03:34,190 --> 00:03:36,800
از شاخص متوسط ​​در آرایه.

66
00:03:36,800 --> 00:03:41,870
>> حالا در اینجا، به یاد داشته باشید که وسط
پارامتر آرایه ارزش است.

67
00:03:41,870 --> 00:03:46,180
بنابراین در اینجا، ما در حال عبور
به روز شده در آرایه ارزش.

68
00:03:46,180 --> 00:03:50,930
این مقادیر به علاوه به علاوه متوسط ​​1 است
در واقع گفت: به صورت بازگشتی تماس بگیرید

69
00:03:50,930 --> 00:03:56,460
جستجو، عبور در یک آرایه جدید، که در آن
که آرایه ای جدید در وسط شروع می شود

70
00:03:56,460 --> 00:03:59,370
به علاوه یکی از اصلی آرایه ارزش های ما.

71
00:03:59,370 --> 00:04:05,400
>> یک ترکیب جایگزین برای که، در حال حاضر که
شما آغاز شده اید برای دیدن اشاره گر است،

72
00:04:05,400 --> 00:04:10,170
ارزش علامت به علاوه وسط 1.

73
00:04:10,170 --> 00:04:17,149
بنابراین، گرفتن آدرس از وسط
به علاوه یک عنصر از ارزش ها.

74
00:04:17,149 --> 00:04:23,690
>> در حال حاضر، اگر شما راحت نیست
اصلاح یک آرایه مانند آن، شما

75
00:04:23,690 --> 00:04:28,900
همچنین می تواند با استفاده از پیاده سازی
یک تابع کمک بازگشتی، که در آن

76
00:04:28,900 --> 00:04:31,680
که تابع کمک کننده طول می کشد
استدلال است.

77
00:04:31,680 --> 00:04:36,610
بنابراین به جای در نظر گرفتن فقط ارزش،
آرایه و اندازه آرایه،

78
00:04:36,610 --> 00:04:42,315
تابع کمکی می تواند بیشتر
استدلال، از جمله شاخص های پایین تر

79
00:04:42,315 --> 00:04:45,280
که شما می توانید در مورد در آرایه مراقبت
و شاخص بالای مراقبت از شما

80
00:04:45,280 --> 00:04:46,300
در مورد آرایه.

81
00:04:46,300 --> 00:04:49,770
>> و به این ترتیب پیگیری هر دو پایین
شاخص و شاخص بالا، شما نمی

82
00:04:49,770 --> 00:04:52,780
نیاز به همیشه تغییر
ارزش های اصلی آرایه.

83
00:04:52,780 --> 00:04:56,390
شما فقط می توانید به ادامه
استفاده از آرایه ارزش.

84
00:04:56,390 --> 00:04:59,540
اما در اینجا، توجه ما را یاور لازم نیست
عمل تا زمانی که ما هستیم

85
00:04:59,540 --> 00:05:01,760
مایل به تغییر اصلی
مقادیر آرایه.

86
00:05:01,760 --> 00:05:05,020
ما مایل به تصویب در است
ارزش ها به روز شد.

87
00:05:05,020 --> 00:05:09,140
>> در حال حاضر، ما نمی توانیم جستجوی دودویی بیش از
یک آرایه است که جستجوی ساده و عادی.

88
00:05:09,140 --> 00:05:12,220
بنابراین، اجازه دهید این مرتب کردن.

89
00:05:12,220 --> 00:05:17,650
در حال حاضر، توجه کنید که مرتب سازی بر گذشته است دو
پارامترهای اعضای هیات ارزش است، که

90
00:05:17,650 --> 00:05:21,110
مجموعه ای که ما در حال طبقه بندی، و int N،
است که طول آرایه است که

91
00:05:21,110 --> 00:05:22,250
ما در حال مرتب سازی.

92
00:05:22,250 --> 00:05:24,840
بنابراین، در اینجا ما می خواهیم برای اجرای
یک الگوریتم مرتب سازی

93
00:05:24,840 --> 00:05:26,690
که ای از n مربع.

94
00:05:26,690 --> 00:05:30,560
شما می توانید به مرتب سازی حبابی، انتخاب را انتخاب کنید
مرتب کردن بر اساس، و یا مرتب سازی بر درج و یا

95
00:05:30,560 --> 00:05:32,670
نوعی دیگر ما ندارد
در کلاس دیده می شود.

96
00:05:32,670 --> 00:05:36,380
اما در اینجا، ما قصد داریم به
استفاده از انتخاب مرتب سازی بر.

97
00:05:36,380 --> 00:05:40,030
>> بنابراین، ما قصد داریم به تکرار
در کل آرایه.

98
00:05:40,030 --> 00:05:44,360
خوب، در اینجا ما می بینیم که ما در حال تکرار
از 0 تا n منهای 1.

99
00:05:44,360 --> 00:05:45,990
چرا تمام راه را تا به N؟

100
00:05:45,990 --> 00:05:49,320
خوب، اگر ما در حال حاضر طبقه بندی شده اند ام اولین
N منهای 1 عناصر، پس از آن

101
00:05:49,320 --> 00:05:54,420
آخرین عنصر آنچه در حال حاضر باید
در محل صحیح، به طوری که مرتب سازی بر

102
00:05:54,420 --> 00:05:56,520
کل آرایه.

103
00:05:56,520 --> 00:05:58,770
>> در حال حاضر، به یاد داشته باشید که چگونه انتخاب
مرتب سازی بر کار می کند.

104
00:05:58,770 --> 00:06:01,950
ما قصد داریم تا بیش از کل آرایه به
به دنبال حداقل مقدار در

105
00:06:01,950 --> 00:06:04,480
آرایه و چوب است که
در آغاز.

106
00:06:04,480 --> 00:06:07,610
پس از آن ما قصد داریم در کل به
آرایه دوباره به دنبال دوم

107
00:06:07,610 --> 00:06:10,410
کوچکترین عنصر، و چوب است که
در جایگاه دوم در

108
00:06:10,410 --> 00:06:12,100
آرایه، و غیره.

109
00:06:12,100 --> 00:06:14,330
بنابراین، این چیزی است که این انجام شده است.

110
00:06:14,330 --> 00:06:17,290
>> در اینجا، ما می بینیم که ما هستیم
تنظیم حداقل در حال حاضر

111
00:06:17,290 --> 00:06:20,030
ارزش به شاخص i ام.

112
00:06:20,030 --> 00:06:23,160
بنابراین در تکرار اول، ما قصد داریم
به در نظر گرفتن حداقل به

113
00:06:23,160 --> 00:06:25,030
شروع آرایه است.

114
00:06:25,030 --> 00:06:28,500
سپس، ما قصد داریم به تکرار بیش از
باقی مانده از آرایه، چک کردن به

115
00:06:28,500 --> 00:06:31,870
ببینید اگر هر کدام از عناصر وجود دارد کوچکتر از
است که ما در حال حاضر است

116
00:06:31,870 --> 00:06:33,900
با توجه به حداقل برساند.

117
00:06:33,900 --> 00:06:38,840
>> بنابراین در اینجا، ارزش J به علاوه یک - که
کمتر از آنچه که ما در حال حاضر

118
00:06:38,840 --> 00:06:40,380
با توجه به حداقل برساند.

119
00:06:40,380 --> 00:06:42,940
پس از آن ما قصد داریم برای به روز رسانی چه
ما فکر می کنیم حداقل به است

120
00:06:42,940 --> 00:06:44,640
صفحه اول J به علاوه 1.

121
00:06:44,640 --> 00:06:48,540
بنابراین، انجام این کار در سراسر آرایه،
و بعد از این حلقه، حداقل

122
00:06:48,540 --> 00:06:53,160
باید حداقل عنصر از است
موقعیت i ام در آرایه.

123
00:06:53,160 --> 00:06:57,350
>> زمانی که ما از آن، ما می توانیم مبادله
حداقل مقدار را در موقعیت i ام

124
00:06:57,350 --> 00:06:58,230
در آرایه.

125
00:06:58,230 --> 00:07:00,130
بنابراین این فقط یک مبادله استاندارد.

126
00:07:00,130 --> 00:07:03,940
ما در یک مقدار به طور موقت ذخیره -
مقدار i ام در آرایه -

127
00:07:03,940 --> 00:07:08,460
قرار داده و به مقدار i ام در آرایه
حداقل ارزش است که متعلق وجود دارد،

128
00:07:08,460 --> 00:07:13,580
و سپس ذخیره را که در آن
مقدار حداقل فعلی استفاده می شود

129
00:07:13,580 --> 00:07:16,460
مقدار i ام در آرایه، پس
که ما آن را از دست دادن نیست.

130
00:07:16,460 --> 00:07:20,510
>> بنابراین، ادامه می دهد که در
تکرار بعدی.

131
00:07:20,510 --> 00:07:23,480
ما شروع به دنبال دوم
حداقل ارزش و وارد است که به

132
00:07:23,480 --> 00:07:24,590
مقام دوم.

133
00:07:24,590 --> 00:07:27,440
در تکرار سوم، ما به دنبال
ارزش حداقل سوم و درج

134
00:07:27,440 --> 00:07:31,550
که به مقام سوم، و غیره
تا زمانی که ما یک آرایه مرتب شده است.

135
00:07:31,550 --> 00:07:33,820
نام من راب است و این
انتخاب مرتب سازی بر بود.

136
00:07:33,820 --> 00:07:39,456