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

2
00:00:13,300 --> 00:00:15,010
>> ROB אודן: היי, אני רוב.

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
כאן, אנו רואים ערך int, שהוא
אמור להיות ערך המשתמש הוא

10
00:00:36,120 --> 00:00:37,320
מחפש.

11
00:00:37,320 --> 00:00:40,800
אנו רואים את מערך ערכי int, אשר
הוא המערך שבו אנחנו

12
00:00:40,800 --> 00:00:42,520
מחפש ערך.

13
00:00:42,520 --> 00:00:45,602
ואנחנו רואים את n int, שהוא
אורכו של המערך שלנו.

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
n, אז זה אורכו של המערך שלנו.

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, ולאחר מכן
מערך חדש יהיה של מינוס הגודל 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
עכשיו, שים לב מסוג זה הוא בעבר שני
פרמטרים int ערכים, המהווה את

90
00:05:17,650 --> 00:05:21,110
מערך שאנחנו ממיינים, וn int,
המהווה את האורך של המערך ש

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
כי הוא o של 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
ובכן, הנה אנחנו רואים שאנחנו iterating
מ -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
י מדד בתוספת 1.

121
00:06:44,640 --> 00:06:48,540
אז, לעשות את זה על פני כל המערך,
ואחרי זה ללולאה, מינימום

122
00:06:48,540 --> 00:06:53,160
צריך להיות האלמנט המינימאלי מ
עמדת i-th במערך.

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-th במערך -

127
00:07:03,940 --> 00:07:08,460
להכניס את ערך i-th במערך
ערך מינימאלי ששייך לשם,

128
00:07:08,460 --> 00:07:13,580
ולאחר מכן לאחסן בחזרה לשם
ערך מינימאלי הנוכחי היה אמור להיות

129
00:07:13,580 --> 00:07:16,460
ערך i-th במערך, כך
שלא לאבד אותו.

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