[Powered by Google Translate] [ابحث عن الخطية]
[باتريك شميد، جامعة هارفارد]
[هذا CS50.] [CS50.TV]
البحث هو الشيء الذي تفعله ربما في كثير من الأحيان مما كنت اعتقد.
من الواضح، في كل مرة تقوم بفتح مستعرض ويب
والبحث عن صفحة ويب -
أو ابحث عن أصدقائك على المفضلة لديك موقع الشبكات الاجتماعية -
تبحث عنه.
ولكن هذا مجرد جزء صغير من البحث الذي قمت به على أساس يومي.
عندما كنت تريد أن تجد أن أحد القميص الأزرق في خزانة،
أو أن بلوزة حمراء مثالية لهذه المناسبة،
أنت تبحث.
عندما تذهب إلى محل لكنت قط من قبل،
وكنت تبحث عن البروكلي في الممر المنتجات
أنت تبحث.
ما قد هل بدأت تلاحظ
هو أن اعتمادا على ما كنت تبحث عن
أو كيف يتم تنظيم العناصر عندما كنت تبحث عنهم
فإنه له تأثير على الطريقة التي بحث.
على سبيل المثال، إذا القمصان الخاصة بك معلقة في خزانة،
ربما يمكنك فقط اختيار من ذلك بكثير دون البحث.
إذا كنت على افتراض عليك أن تسير في الممر
للحصول على القرنبيط، وربما لديك للنظر في جميع الخضروات وغيرها
قبل أن تجد أن القرنبيط.
البحث الخطي هو مثال على أسلوب واحد من هذا القبيل البحث - أو الخوارزمية.
كما يوحي الاسم،
هذا الأسلوب يبحث عن عنصر بطريقة خطية، واحدة تلو الأخرى.
لذا، عندما كنت تبحث في نتائج من محرك البحث المفضل لديك
وتقرأ أسفل قائمة النتائج،
كنت تستخدم البحث الخطي.
حسنا. دعونا ننظر إلى مثال على ذلك.
يقول لدينا قائمة من الأرقام - 2، 4، 0، 5، 3، 7، 8، و 1 -
ونحن نبحث عن 0 عدد.
من الواضح، يمكنك ان ترى فقط أن 0 هو في المركز الثالث.
ولكن، برنامج كمبيوتر ليست محظوظة.
يمكن فقط "رؤية" رقم واحد في كل مرة.
لذلك، ابتداء من بداية القائمة،
فقط "يرى" 2.
البرنامج ثم يتحقق - هو 2 يساوي 0؟
بالطبع لا. لذلك يذهب إلى الرقم التالي، 4.
لا يساوي 4 0؟ كلا.
المرحلة التالية، 0. آه! صفر يساوي 0.
يوجد لدينا هو! انها في المركز الثالث.
حسنا. دعونا نلقي نظرة على بعض شبة الكود.
انها فقط بضع طوابير طويلة، ولكن دعونا ننظر في الأمر سطر واحد في كل مرة.
أولا، دعونا تعريف وظيفة - ونحن في طريقنا للبحث خطي يطلق عليه -
ويستغرق حجتين - الرئيسية والصفيف.
المفتاح هو أن القيمة التي نحن نبحث عن،
حتى في المثال السابق، هو أن الصفر.
مجموعة قائمة من الأرقام
أن لديه كل القيم التي نحن في طريقنا للبحث.
لذلك، ما نريد القيام به هو أننا نريد أن ننظر إلى -
من جميع المناصب، ابتداء من ذلك في البداية من الصفيف
سمسم النهاية من الصفيف - وبالتالي فإن طول الصفيف -
ننظر في كل موقف واحد والتحقق من كل واحد.
بحيث أن هذا ما "ل" حلقة يقوم به.
وفي كل موقف، ونحن في طريقنا إلى القول
"هل هذا قيمة في ذلك الموضع الحالي يساوي المفتاح الذي نبحث عنه؟"
لذلك - في المثال السابق مرة أخرى، وكان مفتاح 0 -
لذلك نحن نقول "هل أنا في موقف مجموعة تساوي الصفر؟"
إذا كان، ونحن في طريقنا للعودة "أنا" لأن هذا هو الوضع الحالي نحن في.
لذلك، في المثال السابق،
كان ذلك المركز الثالث.
إذا نحن قد ذهبت من خلال مجموعة كاملة
ونحن لم نجد أي شيء -
لذلك دعونا نقول كنا نبحث عن عدد 500
الذي كان واضحا في أن لا سبيل المثال -
لدينا للعودة شيء،
ونحن في طريقنا للعودة -1.
ونحن عاد للتو -1 لأن هذا هو الموقف
غير موجود في الصفيف.
وذلك يعني أن عند الحصول على إعادته من وظيفة
تقول "هم، حسنا. اعتقد انني لم أجد أي شيء.
ذلك أن 500 لم يكن هناك ".
والشيء الجميل في البحث هو أن الخطية
وأنها سوف تعمل على أي قائمة للمنتجات،
بغض النظر عن كيفية ترتيب العناصر.
لا يهم حيث البروكلي هو في الممر المنتجات.
طالما كنت السير في الممر من البداية وحتى النهاية،
كنت ملزمة للعثور عليه،
على افتراض المخزن لم ينفد من القرنبيط، بطبيعة الحال.
ولكن أعظم قوة انها هي أيضا أكبر نقطة ضعف الامر.
ويقول لديك قائمة مائتي أرقام
يتم تصنيف أنه اعتبارا من 1 إلى 200.
إذا كنت تبحث عن رقم 198،
لديك للبحث القائمة بأكملها تقريبا من الأرقام
قبل أن تجد الشخص الذي تبحث عنه.
يجب أن يكون هناك طريقة أفضل!
أكد بقية هناك.
ولكن، وهذا هو الموضوع لفيديو آخر.
أيضا، لا تأكل!
لمجرد البحث خطية ليست الحل الأمثل في جميع الحالات،
وهذا لا يعني أن لا يأتي ذلك في متناول يدي.
وإلا، كيف تجد أن البروكلي في الممر المنتجات؟
اسمي باتريك شميد، وهذا هو CS50.
[CS50.TV]