1
00:00:00,000 --> 00:00:08,532
>> [השמעת מוסיקה]

2
00:00:08,532 --> 00:00:12,060
>> ZAMYLA צ'אן: הדבר הראשון שאתה עשוי
הודעה על תגלית היא שאנחנו כבר

3
00:00:12,060 --> 00:00:13,450
יש קוד שנכתב עבורנו.

4
00:00:13,450 --> 00:00:15,160
זה נקרא קוד הפצה.

5
00:00:15,160 --> 00:00:18,000
אז אנחנו לא רק בכתיבה שלנו
קוד מחדש יותר.

6
00:00:18,000 --> 00:00:22,800
במקום זאת, אנחנו רק ממלאים את החללים
בחלק הקוד קיים מראש.

7
00:00:22,800 --> 00:00:27,790
>> תכנית find.c מבקשת עבור מספרים
כדי למלא את ערימת שחת, חיפושים

8
00:00:27,790 --> 00:00:32,189
ערימת שחת למחט משתמש שהוגש,
והוא עושה זאת על ידי קריאה ומיון

9
00:00:32,189 --> 00:00:35,590
חיפוש, פונקציות מוגדרות
בhelpers.c.

10
00:00:35,590 --> 00:00:37,670
אז find.c נכתב כבר.

11
00:00:37,670 --> 00:00:40,770
התפקיד שלך הוא לכתוב עוזרים.

12
00:00:40,770 --> 00:00:41,870
>> אז מה אנחנו עושים?

13
00:00:41,870 --> 00:00:44,210
אנחנו מיישמים שתי פונקציות.

14
00:00:44,210 --> 00:00:49,030
חיפוש, שמחזיר true אם ערך
הוא נמצא בערימת השחת, חוזרים

15
00:00:49,030 --> 00:00:51,370
שקר אם הערך הוא
לא בערימת השחת.

16
00:00:51,370 --> 00:00:57,990
ואז אנחנו גם מיישמים סוג
אשר ממיין את המערך בשם ערכים.

17
00:00:57,990 --> 00:00:59,960
>> אז בואו להתמודד עם חיפוש.

18
00:00:59,960 --> 00:01:04,560
חיפוש כיום מיושם כ
חיפוש ליניארי, אבל אתה יכול לעשות הרבה

19
00:01:04,560 --> 00:01:05,550
יותר טוב מזה.

20
00:01:05,550 --> 00:01:09,910
חיפוש ליניארי מיושם בO
זמן n, וזה די איטי.

21
00:01:09,910 --> 00:01:13,850
אמנם, זה יכול לחפש
כל רשימה שניתנה לו.

22
00:01:13,850 --> 00:01:20,130
התפקיד שלך הוא ליישם חיפוש בינארי,
שיש להפעיל בזמן O של n יומן.

23
00:01:20,130 --> 00:01:21,130
זה די מהר.

24
00:01:21,130 --> 00:01:23,170
>> אבל יש תניה.

25
00:01:23,170 --> 00:01:27,600
חיפוש בינארי יכול רק לחפש
באמצעות רשימות ממוינות.

26
00:01:27,600 --> 00:01:30,370
מדוע זה כך?

27
00:01:30,370 --> 00:01:32,620
>> ובכן בואו נסתכל על דוגמא.

28
00:01:32,620 --> 00:01:36,280
בהינתן מערך של ערכים, בערימת השחת,
אנחנו הולכים להיות מסתכלים

29
00:01:36,280 --> 00:01:37,130
למחט.

30
00:01:37,130 --> 00:01:40,460
ובדוגמה זו,
השלם שלוש.

31
00:01:40,460 --> 00:01:44,130
אופן שבו חיפוש בינארי עובד הוא ש
אנו משווים את ערך אמצע

32
00:01:44,130 --> 00:01:48,370
המערך למחט, כמו איך
פתחנו ספר טלפונים ועד לאמצע

33
00:01:48,370 --> 00:01:50,660
דף בשבוע אפס.

34
00:01:50,660 --> 00:01:54,650
>> אז לאחר שהשווה הערך לאמצע
את המחט, אתה יכול להשליך גם

35
00:01:54,650 --> 00:01:58,530
שמאל או חצי הימני של המערך
על ידי הידוק הגבולות שלך.

36
00:01:58,530 --> 00:02:03,390
במקרה זה, שכן שלוש, המחט שלנו,
הוא פחות מ -10, ערך האמצע,

37
00:02:03,390 --> 00:02:05,990
ימין מאוגד יכול להקטין.

38
00:02:05,990 --> 00:02:08,400
אבל לנסות להפוך את הגבולות שלך
חזק ככל האפשר.

39
00:02:08,400 --> 00:02:11,630
אם הערך האמצעי הוא לא המחט,
אז אתה יודע שאתה לא צריך

40
00:02:11,630 --> 00:02:13,010
לכלול אותו בחיפוש שלך.

41
00:02:13,010 --> 00:02:17,310
אז אתה צודק מאוגד יכול להדק את
גבולות חיפוש רק טיפה יותר,

42
00:02:17,310 --> 00:02:21,770
וכן הלאה וכן הלאה עד
אתה מוצא את המחט שלך.

43
00:02:21,770 --> 00:02:23,480
>> אז מה עושה את pseudocode נראה?

44
00:02:23,480 --> 00:02:28,420
גם בזמן שאנחנו עדיין מחפשים דרך
הרשימה ועדיין יש אלמנטים

45
00:02:28,420 --> 00:02:33,690
נראה ב, אנחנו לוקחים את אמצע הרשימה,
ולהשוות את זה הערך אמצעי ל

46
00:02:33,690 --> 00:02:34,950
המחט שלנו.

47
00:02:34,950 --> 00:02:37,310
אם הם שווים, אז זה אומר שיש לנו
מצאתי את המחט ושאנחנו יכולים

48
00:02:37,310 --> 00:02:38,990
החזר אמיתי.

49
00:02:38,990 --> 00:02:42,870
>> אחרת, אם המחט היא פחות מ
הערך האמצעי, אז זה אומר שאנו

50
00:02:42,870 --> 00:02:47,280
יכול לבטל את החצי הימני, ורק
חיפוש בצד השמאלי של המערך.

51
00:02:47,280 --> 00:02:51,090
אחרת, נצטרך לחפש
צד ימני של המערך.

52
00:02:51,090 --> 00:02:54,410
ובסופו של הדבר, אם אין לך שום
יותר אלמנטים יצאו לחפש אבל אתה

53
00:02:54,410 --> 00:02:58,050
לא מצאת המחט שלך עדיין, אז אתה
בתמורת שווא בגלל המחט

54
00:02:58,050 --> 00:03:01,890
בהחלט לא בערימת השחת.

55
00:03:01,890 --> 00:03:05,270
>> עכשיו דבר מסודר על pseudocode זה
בחיפוש בינארי הוא שזה יכול להיות

56
00:03:05,270 --> 00:03:09,940
להתפרש כאו איטרטיבי
או יישום רקורסיבית.

57
00:03:09,940 --> 00:03:13,810
אז זה יהיה רקורסיבית אם אתה נקרא
פונקציית החיפוש בתוך החיפוש

58
00:03:13,810 --> 00:03:17,350
לתפקד משני מחצית מהמערך.

59
00:03:17,350 --> 00:03:21,030
אנחנו נכסה רקורסיה קצת מאוחר יותר ב
כמובן, אבל יודע שזה

60
00:03:21,030 --> 00:03:24,190
אפשרות אם אתה רוצה לנסות.

61
00:03:24,190 --> 00:03:26,030
>> עכשיו בואו נסתכל על מיון.

62
00:03:26,030 --> 00:03:30,750
מיון לוקח מערך ומספר שלם
n, שהוא בגודל של המערך.

63
00:03:30,750 --> 00:03:34,030
עכשיו יש סוגים שונים שונים
של מיני, ואתה יכול להסתכל על כמה

64
00:03:34,030 --> 00:03:36,370
מכנסיים קצרים להדגמות והסברים.

65
00:03:36,370 --> 00:03:39,580
סוג התמורה לנו
פונקצית מיון היא מבוטלת.

66
00:03:39,580 --> 00:03:43,580
אז זה אומר שאנחנו לא הולכים
לחזור כל מערך מסוג זה.

67
00:03:43,580 --> 00:03:48,140
אנחנו באמת הולכים לשנות מאוד
מערך שהועבר אלינו.

68
00:03:48,140 --> 00:03:52,290
>> וזה אפשרי, כי מערכים הם
עברנו על ידי התייחסות בC. עכשיו אנו

69
00:03:52,290 --> 00:03:55,290
לראות יותר על זה בהמשך, אבל
הבדל מהותי בין פטירתו

70
00:03:55,290 --> 00:03:59,340
במשהו כמו שלם וחולף
במערך, הוא שכאשר אתה

71
00:03:59,340 --> 00:04:03,490
עוברים במספר שלם, C הוא רק הולך
ליצור עותק של המספר שלם ולהעביר

72
00:04:03,490 --> 00:04:04,450
אותו לתפקיד.

73
00:04:04,450 --> 00:04:08,530
המשתנה המקורי לא ישתנה
ברגע שהפונקציה סיימה.

74
00:04:08,530 --> 00:04:12,480
עם מערך, ומצד שני, זה
לא הולך לעשות העתק, ואתה

75
00:04:12,480 --> 00:04:17,910
בעצם להיות עורך
מאוד מערך עצמו.

76
00:04:17,910 --> 00:04:21,269
>> אז סוג אחד של מיון הוא
מיון הבחירה.

77
00:04:21,269 --> 00:04:24,750
מיון הבחירה עובד על ידי החל מהשעה
ההתחלה, ואז אתה לחזר

78
00:04:24,750 --> 00:04:26,820
שוב ולמצוא את האלמנט הקטן ביותר.

79
00:04:26,820 --> 00:04:30,710
ואז אתה להחליף כי הקטן ביותר
אלמנט עם הראשון.

80
00:04:30,710 --> 00:04:34,360
ואז אתה עובר למרכיב השני
, למצוא הבא הקטן ביותר

81
00:04:34,360 --> 00:04:38,320
אלמנט, ולאחר מכן להחליף את זה עם
מרכיב שני במערך בגלל

82
00:04:38,320 --> 00:04:41,100
האלמנט הראשון כבר ממוין.

83
00:04:41,100 --> 00:04:45,370
וכן אז אתה ממשיך לכל
אלמנט בזיהוי הקטן ביותר

84
00:04:45,370 --> 00:04:47,690
ערך ולהחליף אותו החוצה.

85
00:04:47,690 --> 00:04:53,460
>> כי אני שווה 0, האלמנט הראשון
לn מינוס 1, אתה הולך כדי להשוות

86
00:04:53,460 --> 00:04:57,820
כל הערך הבא אחרי זה ולמצוא
המדד של הערך המינימאלי.

87
00:04:57,820 --> 00:05:02,520
ברגע שתמצא את אינדקס הערך המינימאלי,
אתה יכול להחליף ערך זה של מערך

88
00:05:02,520 --> 00:05:05,930
I. מינימום והמערך

89
00:05:05,930 --> 00:05:09,760
>> סוג נוסף מסוג זה שאתה יכול
ליישם הוא מיון בועות.

90
00:05:09,760 --> 00:05:14,380
אז סובב מיון בועות על הרשימה
השוואת מרכיבים וצמודים

91
00:05:14,380 --> 00:05:17,720
החלפת האלמנטים ש
הם בסדר הלא נכון.

92
00:05:17,720 --> 00:05:22,380
ודרך זו, המרכיב הגדול ביותר
תהיה בועה עד הסוף.

93
00:05:22,380 --> 00:05:28,070
והרשימה ממוינת פעם אחת לא יותר
אלמנטים כבר החליפו.

94
00:05:28,070 --> 00:05:31,920
>> אז אלה הם שתי דוגמאות מסוג
אלגוריתמים שתוכלו ליישם עבור

95
00:05:31,920 --> 00:05:33,230
תכנית התגלית.

96
00:05:33,230 --> 00:05:37,350
לאחר שתסיים למיין, ויש לך
עשה חיפוש, אתה גמור.

97
00:05:37,350 --> 00:05:39,720
השם שלי הוא Zamyla, וזה CS50.

98
00:05:39,720 --> 00:05:46,987
>> [השמעת מוסיקה]