1
00:00:00,000 --> 00:00:02,430
[Powered by Google Translate] [ابحث عن الخطية]

2
00:00:02,430 --> 00:00:04,430
[باتريك شميد، جامعة هارفارد]

3
00:00:04,430 --> 00:00:07,430
[هذا CS50.] [CS50.TV]

4
00:00:07,430 --> 00:00:09,440
البحث هو الشيء الذي تفعله ربما في كثير من الأحيان مما كنت اعتقد.

5
00:00:09,440 --> 00:00:11,600
من الواضح، في كل مرة تقوم بفتح مستعرض ويب

6
00:00:11,600 --> 00:00:12,890
والبحث عن صفحة ويب -

7
00:00:12,890 --> 00:00:15,620
أو ابحث عن أصدقائك على المفضلة لديك موقع الشبكات الاجتماعية -

8
00:00:15,620 --> 00:00:16,610
تبحث عنه.

9
00:00:16,610 --> 00:00:19,690
ولكن هذا مجرد جزء صغير من البحث الذي قمت به على أساس يومي.

10
00:00:19,690 --> 00:00:21,720
عندما كنت تريد أن تجد أن أحد القميص الأزرق في خزانة،

11
00:00:21,720 --> 00:00:23,620
أو أن بلوزة حمراء مثالية لهذه المناسبة،

12
00:00:23,620 --> 00:00:24,730
أنت تبحث.

13
00:00:24,730 --> 00:00:26,640
عندما تذهب إلى محل لكنت قط من قبل،

14
00:00:26,640 --> 00:00:28,590
وكنت تبحث عن البروكلي في الممر المنتجات

15
00:00:28,590 --> 00:00:29,650
أنت تبحث.

16
00:00:29,650 --> 00:00:31,050
ما قد هل بدأت تلاحظ

17
00:00:31,050 --> 00:00:32,820
هو أن اعتمادا على ما كنت تبحث عن

18
00:00:32,820 --> 00:00:35,340
أو كيف يتم تنظيم العناصر عندما كنت تبحث عنهم

19
00:00:35,340 --> 00:00:37,670
فإنه له تأثير على الطريقة التي بحث.

20
00:00:37,670 --> 00:00:40,990
على سبيل المثال، إذا القمصان الخاصة بك معلقة في خزانة،

21
00:00:40,990 --> 00:00:42,840
ربما يمكنك فقط اختيار من ذلك بكثير دون البحث.

22
00:00:42,840 --> 00:00:45,300
إذا كنت على افتراض عليك أن تسير في الممر

23
00:00:45,300 --> 00:00:48,750
للحصول على القرنبيط، وربما لديك للنظر في جميع الخضروات وغيرها

24
00:00:48,750 --> 00:00:49,940
قبل أن تجد أن القرنبيط.

25
00:00:49,940 --> 00:00:54,320
البحث الخطي هو مثال على أسلوب واحد من هذا القبيل البحث - أو الخوارزمية.

26
00:00:54,320 --> 00:00:55,550
كما يوحي الاسم،

27
00:00:55,550 --> 00:00:59,240
هذا الأسلوب يبحث عن عنصر بطريقة خطية، واحدة تلو الأخرى.

28
00:00:59,240 --> 00:01:02,080
لذا، عندما كنت تبحث في نتائج من محرك البحث المفضل لديك

29
00:01:02,080 --> 00:01:03,850
وتقرأ أسفل قائمة النتائج،

30
00:01:03,850 --> 00:01:05,290
كنت تستخدم البحث الخطي.

31
00:01:05,290 --> 00:01:06,830
حسنا. دعونا ننظر إلى مثال على ذلك.

32
00:01:06,830 --> 00:01:12,600
يقول لدينا قائمة من الأرقام - 2، 4، 0، 5، 3، 7، 8، و 1 -

33
00:01:12,600 --> 00:01:15,100
ونحن نبحث عن 0 عدد.

34
00:01:15,100 --> 00:01:17,290
من الواضح، يمكنك ان ترى فقط أن 0 هو في المركز الثالث.

35
00:01:17,290 --> 00:01:19,790
ولكن، برنامج كمبيوتر ليست محظوظة.

36
00:01:19,790 --> 00:01:22,030
يمكن فقط "رؤية" رقم واحد في كل مرة.

37
00:01:22,030 --> 00:01:23,840
لذلك، ابتداء من بداية القائمة،

38
00:01:23,840 --> 00:01:25,000
فقط "يرى" 2.

39
00:01:25,000 --> 00:01:27,860
البرنامج ثم يتحقق - هو 2 يساوي 0؟

40
00:01:27,860 --> 00:01:30,320
بالطبع لا. لذلك يذهب إلى الرقم التالي، 4.

41
00:01:30,320 --> 00:01:33,320
لا يساوي 4 0؟ كلا.

42
00:01:33,320 --> 00:01:35,460
المرحلة التالية، 0. آه! صفر يساوي 0.

43
00:01:35,460 --> 00:01:36,920
يوجد لدينا هو! انها في المركز الثالث.

44
00:01:36,920 --> 00:01:39,660
حسنا. دعونا نلقي نظرة على بعض شبة الكود.

45
00:01:39,660 --> 00:01:43,320
انها فقط بضع طوابير طويلة، ولكن دعونا ننظر في الأمر سطر واحد في كل مرة.

46
00:01:43,320 --> 00:01:46,740
أولا، دعونا تعريف وظيفة - ونحن في طريقنا للبحث خطي يطلق عليه -

47
00:01:46,740 --> 00:01:49,040
ويستغرق حجتين - الرئيسية والصفيف.

48
00:01:49,040 --> 00:01:50,770
المفتاح هو أن القيمة التي نحن نبحث عن،

49
00:01:50,770 --> 00:01:53,160
حتى في المثال السابق، هو أن الصفر.

50
00:01:53,160 --> 00:01:55,080
مجموعة قائمة من الأرقام

51
00:01:55,080 --> 00:01:57,180
أن لديه كل القيم التي نحن في طريقنا للبحث.

52
00:01:57,180 --> 00:02:00,010
لذلك، ما نريد القيام به هو أننا نريد أن ننظر إلى -

53
00:02:00,010 --> 00:02:02,030
من جميع المناصب، ابتداء من ذلك في البداية من الصفيف

54
00:02:02,030 --> 00:02:05,260
سمسم النهاية من الصفيف - وبالتالي فإن طول الصفيف -

55
00:02:05,260 --> 00:02:07,580
ننظر في كل موقف واحد والتحقق من كل واحد.

56
00:02:07,580 --> 00:02:10,000
بحيث أن هذا ما "ل" حلقة يقوم به.

57
00:02:10,000 --> 00:02:11,150
وفي كل موقف، ونحن في طريقنا إلى القول

58
00:02:11,150 --> 00:02:15,010
"هل هذا قيمة في ذلك الموضع الحالي يساوي المفتاح الذي نبحث عنه؟"

59
00:02:15,010 --> 00:02:17,000
لذلك - في المثال السابق مرة أخرى، وكان مفتاح 0 -

60
00:02:17,000 --> 00:02:21,770
لذلك نحن نقول "هل أنا في موقف مجموعة تساوي الصفر؟"

61
00:02:21,770 --> 00:02:24,640
إذا كان، ونحن في طريقنا للعودة "أنا" لأن هذا هو الوضع الحالي نحن في.

62
00:02:24,640 --> 00:02:25,710
لذلك، في المثال السابق،

63
00:02:25,710 --> 00:02:27,250
كان ذلك المركز الثالث.

64
00:02:27,250 --> 00:02:29,330
إذا نحن قد ذهبت من خلال مجموعة كاملة

65
00:02:29,330 --> 00:02:30,690
ونحن لم نجد أي شيء -

66
00:02:30,690 --> 00:02:32,180
لذلك دعونا نقول كنا نبحث عن عدد 500

67
00:02:32,180 --> 00:02:33,860
الذي كان واضحا في أن لا سبيل المثال -

68
00:02:33,860 --> 00:02:35,860
لدينا للعودة شيء،

69
00:02:35,860 --> 00:02:37,140
ونحن في طريقنا للعودة -1.

70
00:02:37,140 --> 00:02:39,750
ونحن عاد للتو -1 لأن هذا هو الموقف

71
00:02:39,750 --> 00:02:40,990
غير موجود في الصفيف.

72
00:02:40,990 --> 00:02:43,940
وذلك يعني أن عند الحصول على إعادته من وظيفة

73
00:02:43,940 --> 00:02:46,500
تقول "هم، حسنا. اعتقد انني لم أجد أي شيء.

74
00:02:46,500 --> 00:02:47,930
ذلك أن 500 لم يكن هناك ".

75
00:02:47,930 --> 00:02:49,700
والشيء الجميل في البحث هو أن الخطية

76
00:02:49,700 --> 00:02:51,060
وأنها سوف تعمل على أي قائمة للمنتجات،

77
00:02:51,060 --> 00:02:52,950
بغض النظر عن كيفية ترتيب العناصر.

78
00:02:52,950 --> 00:02:55,540
لا يهم حيث البروكلي هو في الممر المنتجات.

79
00:02:55,540 --> 00:02:57,070
طالما كنت السير في الممر من البداية وحتى النهاية،

80
00:02:57,070 --> 00:02:58,470
كنت ملزمة للعثور عليه،

81
00:02:58,470 --> 00:03:00,800
على افتراض المخزن لم ينفد من القرنبيط، بطبيعة الحال.

82
00:03:00,800 --> 00:03:04,200
ولكن أعظم قوة انها هي أيضا أكبر نقطة ضعف الامر.

83
00:03:04,200 --> 00:03:05,340
ويقول لديك قائمة مائتي أرقام

84
00:03:05,340 --> 00:03:06,930
يتم تصنيف أنه اعتبارا من 1 إلى 200.

85
00:03:06,930 --> 00:03:09,420
إذا كنت تبحث عن رقم 198،

86
00:03:09,420 --> 00:03:11,060
لديك للبحث القائمة بأكملها تقريبا من الأرقام

87
00:03:11,060 --> 00:03:12,960
قبل أن تجد الشخص الذي تبحث عنه.

88
00:03:12,960 --> 00:03:14,460
يجب أن يكون هناك طريقة أفضل!

89
00:03:14,460 --> 00:03:15,890
أكد بقية هناك.

90
00:03:15,890 --> 00:03:17,440
ولكن، وهذا هو الموضوع لفيديو آخر.

91
00:03:17,440 --> 00:03:19,280
أيضا، لا تأكل!

92
00:03:19,280 --> 00:03:22,650
لمجرد البحث خطية ليست الحل الأمثل في جميع الحالات،

93
00:03:22,650 --> 00:03:24,190
وهذا لا يعني أن لا يأتي ذلك في متناول يدي.

94
00:03:24,190 --> 00:03:27,130
وإلا، كيف تجد أن البروكلي في الممر المنتجات؟

95
00:03:27,130 --> 00:03:29,910
اسمي باتريك شميد، وهذا هو CS50.

96
00:03:29,910 --> 00:03:32,000
[CS50.TV]