ما هو البحث الاستيفائي (Interpolation Search)؟ شرح مبسّط مع مثال وكود

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

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

كيف تعمل الخوارزمية؟

بدل اختيار المنتصف، يحسب البحث الاستيفائي موقعاً متوقعاً pos باستخدام هذه المعادلة:

pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])

حيث low وhigh حدّا المجال الحالي، وkey القيمة المطلوبة، وarr المصفوفة المرتبة. المعادلة ببساطة تسأل: "أين تقع قيمتي نسبياً بين أصغر قيمة وأكبر قيمة في المجال؟" ثم تسقط هذه النسبة على المؤشرات. بعد حساب pos:

1. إذا كانت arr[pos] تساوي المطلوب، انتهى البحث ونعيد الموقع.
2. إذا كانت أصغر من المطلوب، نتجاهل النصف الأيسر ونجعل low = pos + 1.
3. إذا كانت أكبر، نتجاهل النصف الأيمن ونجعل high = pos - 1.

ونكرّر حتى نجد القيمة أو يصبح المجال فارغاً.

مثال خطوة بخطوة

لنفترض المصفوفة [10, 20, 30, 40, 50, 60, 70] ونبحث عن 60. القيم موزّعة بانتظام مثالي (الفرق ثابت = 10):

• low = 0، high = 6، أي arr[low] = 10 وarr[high] = 70.
• نحسب: pos = 0 + ((60 - 10) × (6 - 0)) / (70 - 10) = (50 × 6) / 60 = 5.
• arr[5] = 60 — القيمة صحيحة من المحاولة الأولى.

البحث الثنائي كان سيبدأ من الموقع 3 (القيمة 40)، ثم يحتاج خطوات إضافية. هنا يظهر تفوّق الاستيفاء عندما يكون التوزيع منتظماً.

تنفيذ صحيح بلغة بايثون

هذه نسخة مكتملة وآمنة (تتفادى القسمة على صفر عندما تتساوى الحدود):

def interpolation_search(arr, key):
    low, high = 0, len(arr) - 1
    while low <= high and arr[low] <= key <= arr[high]:
        if low == high:
            return low if arr[low] == key else -1
        pos = low + (key - arr[low]) * (high - low) // (arr[high] - arr[low])
        if arr[pos] == key:
            return pos
        elif arr[pos] < key:
            low = pos + 1
        else:
            high = pos - 1
    return -1

الشرط arr[low] <= key <= arr[high] مهم: فهو يوقف البحث فوراً إذا كانت القيمة خارج المجال، ويمنع حساب pos خارج الحدود.

البحث الاستيفائي أم البحث الثنائي؟

المعيار	البحث الاستيفائي	البحث الثنائي
متوسط التعقيد الزمني	O(log log n) مع توزيع منتظم	O(log n) دائماً
أسوأ حالة	O(n) مع توزيع غير منتظم	O(log n)
نوع البيانات	أرقام قابلة للحساب حسابياً	أي قيم قابلة للمقارنة
الحساسية للتوزيع	عالية جداً	لا يتأثر بالتوزيع
التعقيد المكاني	O(1)	O(1)
سهولة التنفيذ	أعقد قليلاً	أبسط وأكثر أماناً

الخلاصة: البحث الثنائي هو الخيار الافتراضي الآمن لأنه ثابت الأداء ويعمل على أي بيانات مرتبة (حتى النصوص). أمّا الاستيفائي فهو تحسين متخصص يتألق فقط في ظروف معيّنة.

متى تستخدمه ومتى تتجنّبه؟

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

تجنّبه عندما يكون التوزيع منحرفاً (skewed). تخيّل مصفوفة مثل [1, 2, 3, 4, 1000000]: عند البحث عن قيمة كبيرة، تدفع المعادلة pos نحو طرف واحد باستمرار، فيتحوّل الأداء عملياً إلى بحث خطي بطيء بتعقيد O(n) — أسوأ من البحث الثنائي. الخطأ الشائع أن يتبنّى المبرمج البحث الاستيفائي لمجرد سماعه أنه "أسرع"، دون التحقق من طبيعة توزيع بياناته. النصيحة العملية: ابدأ دائماً بالبحث الثنائي، ولا تنتقل إلى الاستيفائي إلا بعد قياس حقيقي يثبت أن بياناتك منتظمة وأن البحث يمثّل عنق زجاجة فعلي.

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

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

لماذا قد يكون أبطأ من البحث الثنائي رغم تعقيده الأفضل؟ لأن O(log log n) هو المتوسط مع توزيع منتظم فقط. مع بيانات منحرفة يتدهور إلى O(n)، بينما يبقى البحث الثنائي ثابتاً عند O(log n) مهما كان التوزيع.

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

هل يصلح للقوائم المترابطة (Linked Lists)؟ لا عملياً. الخوارزمية تعتمد على الوصول العشوائي الفوري لأي موقع arr[pos]، وهو غير متاح في القوائم المترابطة، لذا تُستخدم على المصفوفات ذات الوصول المباشر.