خوارزمية البحث الخطي هي إحدى خوارزميات البحث التقليدية و الأساسية، إذ تُعتبر طريقة للبحث عن موقع قيمة معينة داخل مصفوفة، و أساسيتها تنبع من إتباعها منهجية بسيطة جداً، فهي تُنجز عملية البحث بالتحقق من كل عنصر بصورة متسلسلة أو كما يروق لمتخصصي الخوارزميات (خطية). تبدأ من بداية المصفوفة و حتى نهايتها
طريقة عمل خوارزمية البحث الخطي
لإجراء البحث الخطي لا بد من توفر عناصر أساسية و هي مصفوفة البحث و العنصر المُراد البحث عنه
بعكس كثير من خوارزميات البحث، لا يتطلب أن تكون مصفوفة البحث مرتبة ترتيباً تصاعدياً أو تنازلياً، هذا لا يعني أن المصفوفة إذا كانت مرتبة فإنها تُخل بأساسيات البحث الخطي، على العكس تماماً، فكل أنواع المصفوفات مرتبة أو غير مرتبة مُرحبٌ بها في خوارزمية البحث الخطي
مصفوفة البحث لها فهرس (Index)، يبدأ من الواحد أو الصفر، لا تختلف كثيراً فالنتيجة واحدة
يبدأ البحث بالتحقق من العنصر الأول هل هو مساوٍ للعُنصر المراد البحث عنه، إذا وُجد العنصر المراد البحث عنه يُحتفظ برقم الفهرس الخاص بالعنصر و تُنهى عملية البحث
إذا لم يُوجد العنصر المراد البحث عنه تنتقل عملية البحث من العنصر الأول في المصفوفة إلى العنصر الثاني ثم الثالث و هكذا إلى أن يكتمل البحث عن العُنصر المراد البحث عنه في كامل المصفوفة
يُرمز لحالة عدم إيجاد العُنصر المراد البحث عنه بقيمة مختلفة عن قيم فهرس المصفوفة، مثلاً إذا كانت المصفوفة بطول 10 عناصر، و تبدأ من 1 إلى 10، فيُرمز إلى حالة عدم إيجاد العنصر المراد البحث عنه بالرقم ( 0 )، لاحظ أنه كما ذُكر سابقاً في النقطة رقم 3، في بعض المصفوفات قد يبدأ الفهرس من الرقم صفر، في هذه الحالة قد يُلجأ إلى الإشارة بالقيمة NULL في حالة عدم إيجاد العنصر المراد البحث عنه
لا تستغرب تكرار المقارنات بحيث أن كل مقارنة وضعت في سطر حيث نُميز عدد المقارنات، معرفتك لعدد المقارنات ضروري لحساب أداء الخوارزمية.
حساب أفضل و أسواء حالة لخوارزمية البحث الخطي
سأختار أن أحسب أسوأ حالة لخوارزمية البحث الخطي إبتداءً: و لكن قبل أن تقرأ التالي، أُفضل أن تُفكر قليلاً و تحاول إستنتاج أسوأ حالة لهذه الخوارزمية، حتى تستطيع معرفة أسوأ حالة أصيغ لك السؤال بهذة الطريقة، ما هي الحالة التي تؤدي إلى أكبر عدد من المقارنات؟
فكر قليلاً … ثُم فكر … فكرت؟
إذا كانت إحابتك هي الحالة التي يكون فيها العُنصر المُراد البحث عنه في الخانة الأخيرة من المصوفة فتكون قد أجبت الإجابة الأكثر شُهرةً في الخطأ و جانبت الصواب بدرجة، ففي هذه الحالة التي ذكرتها يكون عدد المقارنات هو طول المصفوفة ناقصاً واحد، n-1.
الصواب هو أن أسوأ حالة لخوارزمية البحث الخطي هي عندما لا يكون العُنصر متواجداً بالمصفوفة، و بالتالي يكون عدد المقارنات يساوي طول المصفوفة n.
فكر قليلاً … ثُم فكر … فكرت؟
إذا كانت إحابتك هي الحالة التي يكون فيها العُنصر المُراد البحث عنه في الخانة الأخيرة من المصوفة فتكون قد أجبت الإجابة الأكثر شُهرةً في الخطأ و جانبت الصواب بدرجة، ففي هذه الحالة التي ذكرتها يكون عدد المقارنات هو طول المصفوفة ناقصاً واحد، n-1.
الصواب هو أن أسوأ حالة لخوارزمية البحث الخطي هي عندما لا يكون العُنصر متواجداً بالمصفوفة، و بالتالي يكون عدد المقارنات يساوي طول المصفوفة n.
أفضل حالة لخوارزمية البحث الخطي هي بما لا يدع مجالاً للشك عندما يوجد العُنصر في أول خانة في المصفوفة، فيكون عد المقارنات هو مقارنة واحدة فقط.
الكود التقريبي لخوارزمية البحث الخطي Linear Search Pseudo Code
def sequentialSearch(alist, item):
for pos in range(len(alist)):
if alist[pos] == item:
return True
return False
