خوارزمية البحث الخطى Linear Search

الهدف 

البحث عن عنصر فى مجموعة من العناصر

مثلًا 

الدخل : [1,20,4,3,2] و 20

الخرج : 0 اي العنصر رقم 1 وقميته 20.

كيف تعمل خوارزمية البحث الخطى

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

مثال على خوارزمية البحث الخطى

الكود باستخدام لغة Python

نلاحظ ان العنصر المراد البحث عنه قد يكون فى اول مكان فى المصفوفة 

مثال  : اذا كنا نبحث عن العدد 10 فى المثال السابق وليس عن 33 

فى هذه الحالة يكون عدد المقارنات هى مقارنة واحدة فقط وتسمى هذه الحالة Best Case

ايضًا قد يتواجد العنصر المراد البحث عنه فى اخر المصفوفة 

مثال : اذا كنا نبحث عن العدد 44 او عدد غير موجود فى المصفوفة فى المثال السابق نلاحظ ان عدد المقارنات هو 10 وهو نفس عدد عناصر المفصوفة وهذه الحالة تسمى Worst Case ونحن فى دراسة الخوارزميات نهتم بهذه الحالة.

زمن التنفيذ لخوارزمية البحث الخطى

تحسين على الخوارزمية

فى حالة اذا كان عناصر المصفوفة مترتبة على سبيل المثال مرتبة تصاعديًا 

فيمكننا اضافة شرط انه اذا كان العنصر الحالى فى المصفوفة اكبر من العنصر المراد البحث عنه فيمكننا التوقف عن البحث 

على سبيل المثال عند البحث عن العنصر 3 فى المصفوفة [1,2,4,10] فعند مقارنة العنصر 3 بالعنصر 4 فنجد ان 4 اكبر من 3 بالتالى لافائدة من اكمال البحث حيث ان باقى العناصر كلها اكبر من 4 وبالتالى لن نجد فيها العنصر 3.

الكود الخاص بالبحث الخطى فى حالة ان المصفوفة مرتبة

ولها ايضًا زمن التنفيذ