ما هي خوارزميات البحث؟
في علم الحاسوب، هناك أنواع مختلفة من خوارزميات البحث المتاحة وطريقة استخدامها تحدد أداء وكفاءة البيانات المتاحة (الطريقة التي يتم بها استخدام البيانات)، تعد خوارزميات البحث خطوة أساسية وجوهرية في الحوسبة التي تتم خطوة بخطوة لتحديد موقع بيانات معينة بين مجموعة البيانات، وتستخدم جميع خوارزميات البحث مفتاح البحث (وهو المطلوب البحث عنه) لإكمال إجراء البحث، ومن المتوقع أن تُرجع الخوارزمية حالتين فإما حالة النجاح عندما يتم العثور على قيمة مفتاح البحث في هياكل البيانات، أو حالة الفشل عندما لا يتم العثور على قيمة مفتاح البحث في هياكل البيانات.
تصنيف خوارزميات البحث:
تم تصميم خوارزميات البحث لفحص أو استرداد عنصر من أي هياكل بيانات حيث يتم تخزينه، إذ يتم البحث عن القيمة الهدف (المفتاح) في مساحة البحث، مثل (جميع الطلاب في الفصل، جميع الأرقام في قائمة معينة)، تعطي هذه العمليات إحدى النتيجتين المحتملتين النجاح أو الفشل، ويتم تصنيف هذه الخوارزميات بشكل أساسي في فئتين وفقًا لنوع عمليات البحث الخاصة بهم، وهم:
- البحث المتسلسل: يتم الوصول إلى كل عنصر مخزّن في القائمة أو المصفوفة بالتسلسل، ويتم فحص كل عنصر، على سبيل المثال: البحث الخطي.
- البحث الفاصل: تم تصميم هذه الخوارزميات خصيصًا للبحث في هياكل البيانات المرتبة، ويعد هذا النوع من خوارزميات البحث أكثر فاعلية من طريقة البحث الخطي، حيث يستهدفون بشكل متكرر مركز بنية البحث، ويقسمون مساحة البحث إلى نصفين، على سبيل المثال: بحث الثنائي.
أنواع خوارزميات البحث:
1- البحث الخطي Linear Search:
البحث الخطي أو البحث المتسلسل، حيث تعتبر خوارزمية البحث الخطي من أبسط خوارزميات البحث، وهي طريقة للعثور على عنصر داخل قائمة، ويتم هذا النوع من خوارزميات البحث بالتسلسل بفحص كل عنصر في القائمة حتى يتم العثور على تطابق أو حتى تنتهي القائمة البحث بأكملها، ويتم إجراء البحث الخطي في أسوأ الأحوال بتعقيد وقت مقداره “(n)O” أي سيتم إجراء مقارنات على الأكثر (n) من المرات، حيث (n) هو طول القائمة.
إذا كان من المرجح أن يتم البحث عن كل عنصر بشكل متساوٍ فإن البحث الخطي له متوسط حالة مقارنات (n + 1/2)، لكن يمكن أن تتأثر الحالة المتوسطة إذا اختلفت احتمالات البحث لكل عنصر، ونادرًا ما يكون البحث الخطي عمليًا؛ لأن خوارزميات ومخططات البحث الأخرى، مثل خوارزمية البحث الثنائي وجداول التجزئة، تسمح بالبحث بشكل أسرع عن جميع القوائم باستثناء القوائم القصيرة.
2- البحث الثنائي Binary Search:
يستخدم هذا النوع من خوارزميات البحث للعثور على موضع قيمة معينة موجودة في مصفوفة مرتبة، تعمل خوارزمية البحث الثنائي على مبدأ “فرق تسد”، وتعتبر أفضل خوارزميات البحث وطريقة فعالة لإيجاد قيمة محددة من مجموعة من العناصر المطلوبة؛ وذلك بسبب سرعتها في البحث (بشرط أن تكون البيانات في شكل مرتبة)، ويُعرف البحث الثنائي أيضًا باسم البحث نصف الفاصل أو البحث اللوغاريتمي.
يبدأ البحث في منتصف المصفوفة وينزل إلى النصف الأول السفلي أو العلوي من هيكل البيانات، إذا كانت القيمة المتوسطة أقل من القيمة المستهدفة، فهذا يعني أن البحث يحتاج أن يكون في الجزء العلوي، وإذا لم يكن الأمر كذلك، فإنه يحتاج إلى النظر إلى الجزء السفلي من المصفوفة.
3- البحث بالقفز Jump Search:
تمامًا مثل البحث الثنائي، تعد خوارزمية البحث بالقفز أحد خوارزميات البحث في المصفوفات المرتبة، الفكرة الأساسية هي التحقق من عدد أقل من العناصر (من البحث الخطي) من خلال القفز إلى الأمام بخطوات ثابتة أو تخطي بعض العناصر بدلاً من البحث في جميع العناصر.
الحجم الأمثل للكتلة التي يجب القفز عليها هو (n√)، هذا يجعل التعقيد الزمني للخوارزمية هو “(n√)O”، ويقع التعقيد الزمني للبحث بالقفز بين البحث الخطي “O(n)” والبحث الثنائي “O (Log n)”، ويعد البحث الثنائي أفضل من البحث بالقفز، ولكن ميزة البحث بالقفز هو أننا ننتقل للخلف مرة واحدة فقط (قد يتطلب البحث الثنائي قفزات تصل إلى “O(Log n)”، ضع في اعتبارك الحالة التي يكون فيها العنصر المراد البحث فيه هو أصغر عنصر أو أصغر من الأصغر، لذلك في الأنظمة التي يكون فيها القفز للوراء مكلفًا (من حيث الوقت)، نستخدم خوارزمية البحث بالقفز.
4- البحث بالاستيفاء Interpolation Search:
بحث بالاستيفاء هو البديل المحسن للبحث الثنائي، وتعمل خوارزمية البحث بالاستيفاء على موضع فحص القيمة المطلوبة، ولكي تعمل هذه الخوارزمية بشكل صحيح، يجب أن يتم جمع البيانات بشكل مرتب (بشكل تصاعدي أو تنازلي) وتوزيعها بالتساوي، إذا تم توزيع العناصر بشكل موحد فأن تعقيد الوقت يكون “O (log log n)”، وفي أسوأ الأحوال يمكن أن يستغرق الأمر حتى “O(n)”.
5- البحث الأسي Exponential Search:
يُعرف البحث الأسي أيضًا باسم البحث المضاعف أو السريع، تُستخدم هذه الآلية للعثور على النطاق الذي قد يوجد فيه مفتاح البحث، وبعد العثور على النطاق المحدد تُستخدم تقنية البحث الثنائي للعثور على الموقع الدقيق لمفتاح البحث، قد يكون اسم خوارزمية البحث هذه مضللًا لأنها تعمل في وقت “O (Log n)” إذ يأتي الاسم من الطريقة التي يبحث بها عن عنصر، إذ تعمل خوارزمية البحث الأسي بشكل أفضل من خوارزمية البحث الثنائي في المصفوفات المحدودة، وأيضًا عندما يكون العنصر المراد البحث عنه أقرب إلى العنصر الأول
من تطبيقات البحث الأسي البحث الثنائي الأسي، وهو مفيد بشكل خاص لعمليات البحث غير المحدودة، حيث يكون حجم لمصفوفة غير محدود.
6- البحث في قائمة فرعية Sublist Search:
يستخدم البحث في القائمة الفرعية لاكتشاف وجود قائمة في قائمة أخرى، لنفترض أن لدينا قائمة ذات عقدة واحدة (لنفرض أنها القائمة الأولى)، ونريد التأكد من أن القائمة موجودة في قائمة أخرى(لنفرض أنها القائمة الثانية)، ثم يمكننا إجراء خوارزمية البحث في القائمة الفرعية للعثور عليها، وبالنظر إلى قائمتين مرتبطتين، تتمثل المهمة في التحقق مما إذا كانت القائمة الأولى موجودة في القائمة الثانية أم لا.
7- بحث فيبوناتشي Fibonacci Search:
تقنية بحث فيبوناتشي هي طريقة للبحث عن الخوارزميات حيث تستخدم المصفوفة المرتبة خوارزمية “فرق تسد” التي تضيّق المواقع المحتملة بمساعدة أرقام فيبوناتشي، ومقارنةً بخوارزمية البحث الثنائي التي تقوم بتقسيم المصفوفة التي تم فرزها إلى جزأين متساويين الحجم، أحدهما يتم فحصه بشكل أكبر، تُقسم خوارزمية بحث فيبوناتشي المصفوفة إلى جزأين لهما أحجام متتالية من أرقام فيبوناتشي، حيث تكون المجموعات غير متساوية.
