1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA تشان: أول شيء كنت قد
إشعار حول الاكتشاف هو أننا بالفعل

3
00:00:13,120 --> 00:00:14,520
وقد مدونة مكتوبة بالنسبة لنا.

4
00:00:14,520 --> 00:00:16,219
وهذا ما يسمى كود التوزيع.

5
00:00:16,219 --> 00:00:19,060
لذلك نحن لسنا مجرد كتابة منطقتنا
رمز من الصفر بعد الآن.

6
00:00:19,060 --> 00:00:23,870
بدلا من ذلك، نحن في ملء الفراغات
في بعض التعليمات البرمجية الموجودة مسبقا.

7
00:00:23,870 --> 00:00:28,860
>> يطالب البرنامج find.c للأرقام
لملء كومة قش، يبحث في

8
00:00:28,860 --> 00:00:33,260
كومة قش عن إبرة المستخدم المقدمة،
وأنه يفعل هذا عن طريق استدعاء نوع و

9
00:00:33,260 --> 00:00:36,660
البحث، وظائف محددة
في helpers.c.

10
00:00:36,660 --> 00:00:38,740
هكذا مكتوب find.c بالفعل.

11
00:00:38,740 --> 00:00:41,840
عملك هو لإرسال المساعدين.

12
00:00:41,840 --> 00:00:42,940
>> فماذا نحن فاعلون؟

13
00:00:42,940 --> 00:00:45,270
نحن تنفيذ وظيفتين.

14
00:00:45,270 --> 00:00:50,110
البحث، والتي ترجع صحيح إذا كانت قيمة
وجدت في كومة قش، والعودة

15
00:00:50,110 --> 00:00:52,430
false إذا كانت القيمة
ليس في كومة قش.

16
00:00:52,430 --> 00:00:59,060
ثم نقوم أيضا بتنفيذ الفرز،
الذي يفرز مجموعة تسمى القيم.

17
00:00:59,060 --> 00:01:01,120
لذلك دعونا معالجة البحث.

18
00:01:01,120 --> 00:01:04,550
>> وينفذ حاليا البحث
كما بحث الخطية.

19
00:01:04,550 --> 00:01:06,620
ولكن يمكنك أن تفعل أفضل من ذلك بكثير.

20
00:01:06,620 --> 00:01:11,610
ويتم تنفيذ البحث في خطي يا ن
الوقت، التي هي بطيئة جدا، على الرغم من أنه

21
00:01:11,610 --> 00:01:14,920
يمكن البحث في أي قائمة معينة لذلك.

22
00:01:14,920 --> 00:01:21,190
عملك هو لتنفيذ البحث الثنائي،
التي تدير الوقت يا من سجل ن.

23
00:01:21,190 --> 00:01:22,200
هذا هو سريع جدا.

24
00:01:22,200 --> 00:01:24,240
>> ولكن هناك شرط.

25
00:01:24,240 --> 00:01:28,910
البحث الثنائية يمكن البحث فقط
من خلال القوائم قبل فرزها.

26
00:01:28,910 --> 00:01:31,450
لماذا؟

27
00:01:31,450 --> 00:01:33,690
حسنا، دعونا ننظر إلى مثال على ذلك.

28
00:01:33,690 --> 00:01:37,350
إعطاء مجموعة من القيم، كومة قش،
ونحن في طريقنا إلى أن تبحث

29
00:01:37,350 --> 00:01:41,510
عن إبرة، وفي هذا
سبيل المثال، صحيح 3.

30
00:01:41,510 --> 00:01:45,220
>> الطريقة التي يعمل البحث الثنائي هو أن
قارنا قيمة منتصف

31
00:01:45,220 --> 00:01:49,430
مجموعة إلى إبرة، يشبه إلى حد كبير كيف
فتحنا دفتر الهاتف إلى منتصف

32
00:01:49,430 --> 00:01:51,720
الصفحة في الأسبوع 0.

33
00:01:51,720 --> 00:01:55,710
وذلك بعد مقارنة القيمة المتوسطة ل
الإبرة، يمكنك تجاهل إما

34
00:01:55,710 --> 00:01:59,620
اليسار أو النصف الأيمن من المصفوفة
من خلال تشديد حدود الخاص بك.

35
00:01:59,620 --> 00:02:04,450
في هذه الحالة، منذ 3، إبرة لدينا، هو
أقل من 10، فإن القيمة المتوسطة، و

36
00:02:04,450 --> 00:02:07,060
منضم الحق يمكن أن تقلل.

37
00:02:07,060 --> 00:02:09,470
>> ولكن في محاولة لجعل حدود لديك
ضيق وقت ممكن.

38
00:02:09,470 --> 00:02:12,690
إذا كانت القيمة المتوسطة ليست إبرة،
ثم انت تعرف ان كنت لا تحتاج إلى

39
00:02:12,690 --> 00:02:14,070
إدراجه في بحثك.

40
00:02:14,070 --> 00:02:18,390
حتى حقك ملزمة يمكن أن تشديد
حدود البحث أكثر قليلا صغيرة،

41
00:02:18,390 --> 00:02:22,840
وهلم جرا وهكذا دواليك، حتى
تجد إبرة الخاص بك.

42
00:02:22,840 --> 00:02:24,580
>> فماذا الزائفة
كود تبدو وكأنها؟

43
00:02:24,580 --> 00:02:28,980
كذلك، بينما نحن لا تزال تبحث عن طريق
القائمة والتي لا تزال

44
00:02:28,980 --> 00:02:33,540
عناصر للنظر في، ونحن نأخذ الوسط
من القائمة وقارن ذلك

45
00:02:33,540 --> 00:02:36,020
القيمة المتوسطة لإبرة لدينا.

46
00:02:36,020 --> 00:02:38,380
لو انهم على قدم المساواة، فإن ذلك يعني أننا قد
العثور على الإبرة، ويمكننا

47
00:02:38,380 --> 00:02:40,160
العودة الحقيقية.

48
00:02:40,160 --> 00:02:43,940
>> خلاف ذلك، إذا كان أقل من إبرة
القيمة المتوسطة، فإن ذلك يعني أننا

49
00:02:43,940 --> 00:02:48,350
يمكن تجاهل النصف الأيمن فقط و
البحث في الجانب الأيسر من مجموعة.

50
00:02:48,350 --> 00:02:51,860
وإلا فإننا سوف ابحث في
الجانب الأيمن من المصفوفة.

51
00:02:51,860 --> 00:02:55,470
وفي النهاية، إذا لم يكن لديك أي
أكثر من عناصر اليسار إلى بحث لكنك

52
00:02:55,470 --> 00:02:58,030
لم يتم العثور على إبرة الخاص بك حتى الآن،
فإنك عودة كاذبة.

53
00:02:58,030 --> 00:03:02,960
لأن الإبرة بالتأكيد
ليس في كومة قش.

54
00:03:02,960 --> 00:03:06,200
>> الآن، شيء واحد أنيق حول هذا الزائفة
التعليمات البرمجية في البحث الثنائي هو أنه يمكن

55
00:03:06,200 --> 00:03:11,000
أن تفسر على أنها إما تكرارية
أو تنفيذ العودية.

56
00:03:11,000 --> 00:03:14,900
لذلك سيكون من العودية إذا كنت تسمى
وظيفة البحث في البحث

57
00:03:14,900 --> 00:03:18,400
تعمل على أي نصف صفيف.

58
00:03:18,400 --> 00:03:20,750
سنقوم تغطية العودية قليلا
في سياق لاحق.

59
00:03:20,750 --> 00:03:23,210
ولكن لا نعرف أنه هو خيار
إذا كنت ترغب في محاولة.

60
00:03:23,210 --> 00:03:24,460