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
البحث، والتي ترجع صحيح إذا كانت قيمة
وجدت في كومة قش، والعودة

15
00:00:49,030 --> 00:00:51,370
false إذا كانت القيمة
ليس في كومة قش.

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
ن الوقت، التي هي بطيئة جدا.

21
00:01:09,910 --> 00:01:13,850
وعلى الرغم من أنه يمكن بحث
أي قائمة محددة لذلك.

22
00:01:13,850 --> 00:01:20,130
عملك هو لتنفيذ البحث الثنائي،
التي تدير الوقت يا من سجل ن.

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
>> فماذا في شبة الكود تبدو وكأنها؟

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
>> الآن الشيء أنيق حول هذا شبة الكود
في البحث الثنائي هو أنه يمكن أن يكون

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
نوع يأخذ مجموعة وصحيح
ن، والذي هو حجم المصفوفة.

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
>> [عزف الموسيقى]