[عزف الموسيقى] DOUG لويد: الخطي البحث هو أننا خوارزمية يمكن استخدامها للعثور على عنصر في صفيف. إستدعاء خوارزمية هو عبارة عن مجموعة خطوة بخطوة من تعليمات لإكمال المهمة. 

البحث الخطي الخوارزمية يعمل على النحو التالي. تكرار عبر مجموعة من اليسار إلى الحق، وتبحث عن عنصر المحدد. 

في شبة الكود، وهو أكثر نسخة المقطر من هذه الجملة، إذا كان العنصر الأول هو ما كنت تبحث عنه، يمكنك التوقف. خلاف ذلك، والانتقال إلى العنصر التالي و الاستمرار مرارا وتكرارا حتى تجد العنصر، أو لم تقم. حتى نتمكن من استخدام خطي خوارزمية البحث، على سبيل المثال، العثور على القيمة المستهدفة تسعة في هذه المجموعة. حسنا نبدأ في البداية. إذا كان ما نحن تبحث عن، فإننا يمكن أن تتوقف. انها ليست، نحن لا نبحث عن 11. لذلك على خلاف ذلك، والانتقال إلى العنصر التالي. 

لذلك نحن ننظر إلى 23. هو 23 ما كنت تبحث عنه؟ حسنا لا، حتى ننتقل الى المرحلة التالية عنصر، والعنصر التالي، ونبقى يمر هذه العملية مرارا وتكرارا وأكثر، حتى أننا الأرض في مثل هذا الوضع. 

تسعة هو ما نبحث عنه، وهذا عنصر من المصفوفة هو، انها القيمة تسعة. ولذلك وجدنا ما نحن عليه تبحث عنها، ونحن يمكن أن تتوقف. البحث الخطي له الانتهاء، بنجاح. 

ولكن ماذا عن إذا كنا نبحث عن أحد العناصر التي ليست في مجموعة لدينا. هل البحث الخطي لا تزال تعمل؟ تأكد جيدا. لذلك نكرر هذه العملية بدءا من العنصر الأول. إذا كان ما نحن تبحث عن، فإننا يمكن أن تتوقف. ليست كذلك. خلاف ذلك، ننتقل إلى العنصر التالي. 

لكننا يمكن أن تبقي تكرار هذه العملية، دراسة كل عنصر بدوره، على أمل أن نجد العدد 50. لكننا لن نعرف إذا وجدنا أن عدد 50 أو إذا لم نفعل، حتى لقد صعدت على كل عنصر واحد من مجموعة. 

فقط مرة واحدة فعلناه أن والخروج قصيرة، يمكننا أن نستنتج أن 50 ليس في المصفوفة. وبالتالي فإن البحث الخطي الخوارزمية، إضافة إلى أنه فشل في حد ذاتها. ولكن ليس بمعنى أنه لم يوفق في فعل ما طلبنا أن تفعله. 

وكانت ناجحة في النحو بقدر ما لم يجد 50، ولكن 50 لم يكن في المصفوفة. ولكننا قد بحثت باستفاضة من خلال كل عنصر واحد وهكذا، في حين أننا لم نجد أي شيء، بحث خطي لا يزال ينجح حتى لو كان العنصر غير موجود في المصفوفة. 

إذن ما هو أسوأ حالة السيناريو مع البحث الخطي؟ كذلك علينا أن ننظر من خلال كل عنصر واحد، إما لأن العنصر المستهدف هو العنصر الأخير للصفيف، أو العنصر الذي نبحث عنه لا موجودة بالفعل في مجموعة على الإطلاق. ما هو أفضل سيناريو؟ كذلك فإننا قد نجد ل العنصر فورا. وعدد العناصر هل لدينا بعد ذلك للبحث في في أفضل الأحوال، إذا كنا نبحث عن ذلك ونجد أنه في البداية؟ نحن يمكن أن تتوقف على الفور. 

ماذا يعني هذا القول عن تعقيد البحث الخطي؟ كذلك في أسوأ الأحوال، لدينا أن ننظر إلى كل عنصر واحد. وبحيث يتم تشغيله في O ل ن، في أسوأ الأحوال. 

في أفضل الأحوال، نحن ستعمل العثور على العنصر فورا. وهكذا يعمل في أوميغا 1. 

أنا دوغ ويد. هذا هو CS50.