البحث الخطي
البحث الخطي هو ما تفعله عندما تبحث عن اسم في قائمة غير مرتبة: تبدأ من الأعلى وتقرأ نزولًا حتى تجده. إنه أبسط بحث على الإطلاق، ويعمل على أي قائمة، وكثيرًا ما يكفي وحده للقوائم القصيرة.
الفكرة
قارن الهدف بالقيمة الأولى في القائمة. إذا تساويا، توقف: الهدف في الموضع 1. وإلا فقارنه بالقيمة الثانية، ثم الثالثة، وهكذا. إذا لم تطابقه القيمة الأخيرة أيضًا، فالهدف ليس في القائمة. لا يلزم معرفة أي شيء عن القائمة مسبقًا: لا يجب أن تكون مرتبة، ويمكن أن تكون القيم أي شيء يمكن مقارنته من حيث التساوي.
مثال
ابحث عن 4 في 5, 1, 4, 2, 8. هل 5 تساوي 4؟ لا. و1؟ لا. و4؟ نعم: وُجدت في الموضع 3 بعد 3 مقارنات. ابحث الآن عن 7 في القائمة نفسها. تُفحص القيم الخمس كلها ولا تطابق أي منها، لذا بعد 5 مقارنات يكون الجواب أن 7 غير موجودة.
كم مقارنة
تحتاج القيمة في الموضع k إلى k مقارنة لإيجادها. إذا كان احتمال وجود الهدف متساويًا في كل المواضع، فالمتوسط (n + 1)/2 مقارنة: 20.5 لـ40 قيمة. أما القيمة غير الموجودة فتحتاج دائمًا إلى n، لأنه لا يُعرف يقينًا أن لا قيمة طابقت إلا بعد المقارنة الأخيرة. لذا تنمو التكلفة بالتناسب مع طول القائمة، وتُكتب O(n).
البحث الأسرع يحتاج إلى ترتيب
لا يستطيع البحث الخطي تخطي أي شيء، لأن أي قيمة في القائمة غير المرتبة قد تكون في أي مكان. أما إذا كانت القائمة مرتبة، فالمقارنة تخبرك بأكثر من التساوي أو عدمه: تخبرك في أي جهة يقع الهدف. يستخدم البحث الثنائي ذلك ليقسم القائمة نصفين في كل خطوة، فيحتاج إلى نحو log₂ n مقارنة، 6 على الأكثر لـ40 قيمة. لكن الترتيب يستغرق وقتًا أيضًا، لذا فالبحث الخطي غالبًا هو الخيار الأفضل لقائمة لا يُبحث فيها إلا مرة واحدة.
تحسينات صغيرة
تضع نسخة الحارس الهدف في نهاية القائمة قبل البحث، فلا تحتاج الحلقة إلا إلى اختبار التطابق، دون اختبار نهاية القائمة أيضًا. ونقل القيمة مكانًا واحدًا نحو بداية القائمة، أو إلى أولها، في كل مرة تُوجد فيها يجعل القيم التي يكثر البحث عنها أرخص مع الوقت. ولا يغيّر أي منهما أسوأ حالة، وهي n مقارنة.
استكشفه
افتح التطبيق، واختر قيمة في «ابحث عن»، واضغط خطوة. يُظهر الخط المتقطع ارتفاع الهدف، وتُميَّز كل قيمة عند فحصها وتبهت بعد استبعادها، ويتحول التطابق إلى الأخضر. ابحث عن قيمة غير موجودة في القائمة لترى فحصًا كاملًا، أو ألغِ تحديد «توقف عند أول تطابق» واستخدم قيمًا مختلفة قليلة لإيجاد عدة تطابقات.
الأسئلة المتداولة
ما التعقيد الزمني للبحث الخطي؟
O(n) في أسوأ حالة وفي المتوسط، وO(1) في أفضل حالة، عندما يكون الهدف القيمة الأولى. ولا يحتاج إلى ذاكرة إضافية.
ما الفرق بين البحث الخطي والبحث الثنائي؟
يفحص البحث الخطي كل القيم بالترتيب ويعمل على أي قائمة. أما البحث الثنائي فلا يعمل إلا على قائمة مرتبة، لكنه يقسم الجزء الذي قد يحوي الهدف نصفين في كل خطوة، فيحتاج إلى نحو log₂ n مقارنة بدلًا من n كحد أقصى.
هل يحتاج البحث الخطي إلى قائمة مرتبة؟
لا، وهذه ميزته الرئيسية. في القائمة المرتبة يمكنه التوقف بمجرد تجاوز الموضع الذي كان يجب أن يكون فيه الهدف، لكنه يظل أبطأ من البحث الثنائي.
أين يُستخدم البحث الخطي؟
في كل مكان تكون فيه القوائم قصيرة أو غير مرتبة: إيجاد عنصر في مصفوفة صغيرة، أو مسح ملف أو تدفق لا يمكن قراءته إلا بالترتيب، أو فحص كل عنصر للتحقق من شرط ما. كثير من دوال المكتبات، مثل indexOf في JavaScript وlist.index في Python، هي عمليات بحث خطي.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب البحث الخطي