ما هو البحث الخطي (Linear Search)؟ شرح مبسّط مع أمثلة عملية

البحث الخطي (Linear Search) هو أبسط خوارزمية للبحث عن عنصر داخل قائمة أو مصفوفة: تمرّ على العناصر واحداً تلو الآخر من البداية إلى النهاية، وتقارن كل عنصر بالقيمة التي تبحث عنها، فإذا وجدتها أعدت موضعها، وإن وصلت إلى آخر القائمة دون أن تجدها استنتجت أنها غير موجودة. لا يشترط أن تكون البيانات مرتبة، وهذا هو سرّ بساطته وسبب استخدامه الواسع في الحالات الصغيرة أو غير المنظّمة.

تعقيده الزمني في أسوأ الحالات هو O(n)، أي أن الوقت يتناسب طردياً مع عدد العناصر. هذا يكفي لفهم متى يكون خياراً ذكياً ومتى يصبح مكلفاً، وهو ما سنفصّله بأمثلة عملية.

كيف يعمل البحث الخطي خطوة بخطوة

تخيّل أنك تبحث عن اسم في قائمة أسماء غير مرتبة أبجدياً. الطريقة الوحيدة المضمونة أن تقرأ اسماً اسماً حتى تصل إليه. هذا بالضبط ما تفعله الخوارزمية:

1. ابدأ من العنصر الأول في القائمة (الموضع 0).
2. قارن العنصر الحالي بالقيمة المطلوبة (target).
3. إن تطابقا، أعِد موضع العنصر وتوقّف.
4. إن لم يتطابقا، انتقل إلى العنصر التالي.
5. كرّر حتى تجد العنصر أو تصل إلى نهاية القائمة.
6. إن انتهت القائمة دون تطابق، أعِد قيمة تدل على عدم الوجود (غالباً ‎-1).

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

مثال عملي بلغة بايثون

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index      # وجدنا العنصر
    return -1                 # لم نجده

numbers = [7, 3, 9, 2, 6]
print(linear_search(numbers, 9))   # النتيجة: 2
print(linear_search(numbers, 4))   # النتيجة: -1

ونفس المنطق بلغة جافاسكريبت:

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

تنبيه شائع: كثيرون يعيدون قيمة منطقية true فقط عند العثور على العنصر، لكن إعادة الموضع (index) أفيد بكثير، لأنه يخبرك أين وجدت العنصر لا مجرد أنه موجود. واعتمد قيمة ‎-1 للدلالة على الغياب لأن أي موضع صحيح يبدأ من الصفر.

التعقيد الزمني ومتى يبطؤ الأداء

• أفضل حالة (Best case): العنصر في أول القائمة، فتنتهي بمقارنة واحدة، والتعقيد O(1).
• أسوأ حالة (Worst case): العنصر في آخر القائمة أو غير موجود، فتفحص كل العناصر، والتعقيد O(n).
• الحالة المتوسطة: نحو نصف العناصر، وتبقى من رتبة O(n).

عملياً، البحث في قائمة من عشرة عناصر لا يُلاحَظ زمنه إطلاقاً. لكن لو كانت القائمة تحوي مليون عنصر، فقد يتطلب في أسوأ الحالات مليون مقارنة، وهنا يبدأ الأداء بالتراجع بشكل ملموس، خصوصاً إذا تكرّر البحث آلاف المرات في الثانية.

ميزة مهمة يغفل عنها كثيرون: البحث الخطي يستهلك ذاكرة إضافية ثابتة O(1)، أي أنه لا يحتاج إلى مساحة تنمو مع حجم البيانات، وهذا يجعله مناسباً للبيئات محدودة الموارد.

البحث الخطي أم البحث الثنائي؟

السؤال الأكثر شيوعاً هو المقارنة مع البحث الثنائي (Binary Search). الفرق الجوهري أن البحث الثنائي أسرع بكثير لكنه يشترط أن تكون البيانات مرتبة مسبقاً.

المعيار	البحث الخطي	البحث الثنائي
اشتراط ترتيب البيانات	لا يشترط	يشترط الترتيب
التعقيد الزمني (أسوأ حالة)	O(n)	O(log n)
سهولة التنفيذ	بسيط جداً	أعقد قليلاً
ملاءمة القوائم الصغيرة	ممتاز	مبالغة غير ضرورية
ملاءمة القوائم الكبيرة المرتبة	ضعيف	ممتاز
العمل على قوائم مترابطة (Linked List)	مناسب	غير عملي

القاعدة العملية: إذا كانت بياناتك صغيرة أو غير مرتبة أو تبحث فيها مرة واحدة، فالبحث الخطي أبسط وأسرع في الكتابة. أما إذا كانت مرتبة وستبحث فيها مراراً، فالاستثمار في ترتيبها ثم استخدام البحث الثنائي يوفّر وقتاً هائلاً.

انتبه إلى مفارقة مهمة: إذا كانت البيانات غير مرتبة أصلاً، فإن ترتيبها يكلّف O(n log n)، وهو أبطأ من بحث خطي واحد بتعقيد O(n). لذلك لا يُجدي الترتيب إلا إذا كنت ستبحث كثيراً في نفس البيانات.

متى تختار البحث الخطي فعلاً

• عندما يكون عدد العناصر صغيراً (بضع عشرات أو مئات).
• عندما تكون البيانات غير مرتبة ولا تنوي ترتيبها.
• عندما تبحث لمرة واحدة فقط ولا يتكرّر البحث.
• عندما تعمل على بنية لا تتيح الوصول العشوائي بكفاءة مثل القوائم المترابطة.
• عندما تريد كوداً واضحاً سهل الصيانة دون تعقيد.

في المشاريع الحقيقية الكبيرة، غالباً ما تلجأ اللغات والمكتبات إلى بنى أسرع مثل جداول التجزئة (Hash Tables) التي تحقق بحثاً بمتوسط O(1). لكن فهم البحث الخطي يبقى الأساس الذي تُبنى عليه بقية خوارزميات البحث، وهو أول ما يُطلب في مقابلات العمل التقنية.

الأسئلة الشائعة

هل البحث الخطي يعمل على البيانات غير المرتبة؟ نعم، وهذه أبرز ميزة له. لا يشترط أي ترتيب مسبق، بينما البحث الثنائي يتطلب قائمة مرتبة ليعمل بشكل صحيح.

ما الفرق بين O(n) وO(log n) عملياً؟ في قائمة من مليون عنصر، قد يحتاج البحث الخطي إلى مليون مقارنة في أسوأ الحالات، بينما يحتاج البحث الثنائي إلى نحو عشرين مقارنة فقط. الفارق يصبح هائلاً كلما كبرت البيانات.

هل يمكن تسريع البحث الخطي؟ تحسينات بسيطة مثل إيقاف البحث فور العثور على العنصر (وهو الأصل) أو ما يُعرف بـ«حارس النهاية» (Sentinel) تقلّل المقارنات قليلاً، لكنها لا تغيّر التعقيد الجوهري O(n).

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