خوارزميات البحث

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

1. البحث التسلسلي Sequential Search: في هذا النوع من البحث يجري التنقل عبر عناصر المصفوفة بالتتابع مع التحقق من كل عنصر فيها، ومن الأمثلة على هذا النوع هو البحث الخطّي Linear Search.
2. البحث المقطعي Interval Search: صُمّمت هذه الخوارزميات تصميمًا خاصًّا للبحث في بنى المعطيات التي تكون مرتّبة. هذه الخوارزميات أكفأ من البحث الخطّي وذلك لأنّها تستهدف منتصف بنية البحث استهدافًا مستمرًّا وتنصّف المساحة المشغولة بواسطة عملية البحث، ومن الأمثلة على هذا النوع هو البحث الثنائي Binary Search.

البحث الخطي

البحث الخطّي Linear Search من أبسط خوارزميات البحث إذ أنّها تمر على عناصر المصفوفة واحدًا تلو الآخر بحثًا عن العنصر المطلوب.

البحث الثنائي

تبحث خوارزمية البحث الثنائي Binary Search عن عنصر معين في مصفوفة مرتبة وذلك بتقسيمها باستمرار إلى نصفين والتحقق من وجود العنصر المراد البحث عنه في كلّ نصفٍ إلى أن تعثر على العنصر أو تصل إلى مصفوفة فارغة.

البحث القفزي

تتحقق خوارزمية البحث القفزي Jump Search (تعرف كذلك بخوارزمية البحث الكتلي Block Search) من عدد أقل من العناصر (مقارنة بالبحث الخطي) وذلك بالقفز عبر عناصر المصفوفة بخطوات ثابتة، بمعنى تجاوز بعض العناصر عوضًا عن البحث فيها كلّها.

البحث الاستكمالي

تعدّ خوارزمية البحث الاستكمالي Interpolation Search تحسينًا على البحث الثنائي في بعض الحالات، إذ تكون القيم موزّعة بانتظام في مصفوفة مرتبة فتجري هذه الخوارزمية عملية التحقّق في مواقع مختلفة بالاعتماد على قيمة المفتاح المراد البحث عنه.

البحث الأسّي

تقسّم خوارزمية البحث الأسّي Exponential Search المصفوفة التي يجري البحث فيها إلى مصفوفات فرعية يزداد عدد العناصر فيها ازديادًا أسّيًا (1, 2, 4, 8.... وهكذا إلى حين الوصول إلى مصفوفة جزئية يكون فيها العنصر الأخير أكبر من العنصر المطلوب.