الهدف
البحث عن عنصر فى مجموعة من العناصر
مثلًا
الدخل : [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.
الكود الخاص بالبحث الخطى فى حالة ان المصفوفة مرتبة
ولها ايضًا زمن التنفيذ