اقرأ في هذا المقال
- مفهوم خوارزمية البحث بالاستيفاء Interpolation Search
- خطوات خوارزمية البحث بالاستيفاء
- تعقيد الوقت لخوارزمية البحث بالاستيفاء
مفهوم خوارزمية البحث بالاستيفاء Interpolation Search:
خوارزمية البحث بالاستيفاء هي في الأساس نسخة محسنة من خوارزمية البحث الثنائي، وكما البحث الثنائي فإن بحث الاستيفاء تعمل فقط على المصفوفة المرتبة، ولكي تعمل هذه الخوارزمية بشكل صحيح، يجب أن تكون مجموعة البيانات في مرتبة وموزعة بشكل متساوي، تنتقل خوارزمية البحث الثنائي دائمًا إلى العنصر الأوسط للتحقق منه، ومن ناحية أخرى، قد تنتقل بحث الاستيفاء إلى مواقع مختلفة وفقًا لقيمة المفتاح الذي يتم البحث عنه، فعلى سبيل المثال، إذا كانت قيمة المفتاح أقرب إلى العنصر الأخير، فمن المحتمل أن يبدأ بحث الاستيفاء البحث باتجاه الجانب الأخير.
وتتمتع خوارزمية البحث الثنائي بميزة كبيرة تتمثل في تعقيد الوقت على خوارزمية البحث الخطي، فخوارزمية البحث الخطي لديها أسوأ حالة تعقيد “Ο(n)” بينما خوارزمية البحث الثنائي لديها “Ο(log n)”، هناك حالات قد يكون فيها موقع بيانات الهدف معروفًا مسبقًا، على سبيل المثال، في حالة دليل الهاتف، وإذا أردنا البحث عن رقم هاتف “Morphius” هنا، سيبدو البحث الخطي وحتى البحث الثنائي بطيئًا حيث يمكننا الانتقال مباشرةً إلى مساحة الذاكرة حيث يتم تخزين الأسماء التي تبدأ من “M”.
خطوات خوارزمية البحث بالاستيفاء:
الخطوة 1: في الـ (loop)، ابدأ البحث عن العنصر (المراد إيجاده) من منتصف القائمة.
الخطوة 2: إذا تتطابق المنتصف مع عنصر البحث، فقم بإرجاع مكان العنصر، واخرج من الـ (loop).
الخطوة 3: إذا لم تكن مطابقة، احسب قيمة “pos” باستخدام صيغة فحص الموضع.
الخطوة 4: قسّم القائمة باستخدام صيغة فحص الموضع وابحث عن الوسط الجديد.
الخطوة 5: إذا كان عنصر أقل من الوسط “arr [pos]”، فاحسب قيمة “pos” للمصفوفة الفرعية اليسرى.
الخطوة 6: إذا كان العنصر أكبر من الوسط “arr [pos]”، فاحسب قيمة “pos” للمصفوفة الفرعية اليمنى.
الخطوة 4: كرر هذه العملية، حتى يتم العثور على تطابق أو حتى تتقلص المصفوفة الفرعية إلى الصفر.
تعقيد الوقت لخوارزمية البحث بالاستيفاء:
تقسم خوارزمية البحث الثنائي مساحة البحث إلى النصف في كل خطوة بغض النظر عن توزيع البيانات، بالتالي تعقيدها الزمني دائمًا “O(log (n))”، من ناحية أخرى، حيث يختلف تعقيد وقت البحث بالاستيفاء اعتمادًا على توزيع البيانات، فهي أسرع من البحث الثنائي في البيانات الموزعة بشكل موحد إذ يكون تعقيدها الزمني في المتوسط “O(log log(n) )” وفي أفضل السيناريوهات “O(1)”، ومع ذلك، في أسوأ السيناريوهات، يمكن أن يكون أداءها ضعيفًا “O(n)”.
