بحث القفز (Jump Search): شرح مبسّط للخوارزمية وكيف تعمل مع أمثلة

بحث القفز (Jump Search) هو خوارزمية للبحث عن عنصر داخل مصفوفة مُرتَّبة، وفكرتها بسيطة: بدل فحص العناصر واحدًا واحدًا كما في البحث الخطي، تقفز الخوارزمية بخطوات ثابتة إلى الأمام حتى تتجاوز قيمة العنصر المطلوب، ثم تعود قفزة واحدة للخلف وتبحث خطيًّا داخل تلك الكتلة الصغيرة. الشرط الأساسي لعملها هو أن تكون البيانات مرتبة تصاعديًّا، وأداؤها الزمني هو O(√n) — أي أسرع من البحث الخطي وأبطأ قليلًا من البحث الثنائي.

الفكرة الأساسية في جملة واحدة

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

لماذا يكون طول القفزة = الجذر التربيعي لحجم المصفوفة؟

هذه النقطة هي جوهر الخوارزمية وكثيرًا ما تُشرح بسطحية. لو كان طول القفزة هو m وحجم المصفوفة n، فإن أسوأ حالة تتضمّن:

• عدد القفزات إلى الأمام ≈ n/m
• عدد المقارنات في البحث الخطي داخل الكتلة الأخيرة ≈ m - 1

المجموع تقريبًا n/m + m. وأقل قيمة لهذا المجموع تتحقق رياضيًّا عندما يكون m = √n، وعندها يصبح إجمالي العمل في حدود 2√n، أي O(√n). لهذا السبب تحديدًا يُختار طول القفزة مساويًا للجذر التربيعي، وليس رقمًا عشوائيًّا.

خطوات عمل الخوارزمية

1. احسب طول القفزة: step = ⌊√n⌋ (الجزء الصحيح من جذر حجم المصفوفة).
2. اقفز إلى الأمام بمقدار step كل مرة، وتحقّق فقط من العنصر الواقع في نهاية كل قفزة.
3. استمرّ في القفز طالما أن قيمة العنصر عند نهاية القفزة أصغر من العنصر المطلوب.
4. عندما تجد عنصرًا أكبر من أو يساوي المطلوب، فأنت الآن تجاوزت الكتلة الصحيحة؛ ارجع إلى بداية هذه الكتلة الأخيرة.
5. ابحث خطيًّا داخل هذه الكتلة فقط. إذا وجدت العنصر أعِد موضعه، وإن انتهت الكتلة دون إيجاده فهو غير موجود.

مثال عملي بالخطوات

لنبحث عن الرقم 55 في المصفوفة المرتبة التالية (16 عنصرًا):

[3, 8, 12, 19, 22, 31, 40, 46, 55, 61, 68, 72, 80, 91, 97, 99]

• حجم المصفوفة n = 16، إذن step = √16 = 4.
• الفهرس 0 قيمته 3 < 55 → اقفز.
• الفهرس 4 قيمته 22 < 55 → اقفز.
• الفهرس 8 قيمته 55… توقّف، لأن 55 ≥ 55.
• ابحث خطيًّا من الفهرس 4 حتى 8، فتجد 55 عند الفهرس 8.

عدد المقارنات هنا أقل بكثير من فحص العناصر الثمانية الأولى واحدًا واحدًا.

مثال بالكود (بايثون)

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    # القفز حتى نتجاوز قيمة الهدف
    while prev < n and arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    # بحث خطي داخل الكتلة
    for i in range(prev, min(step, n)):
        if arr[i] == target:
            return i
    return -1

مقارنة: بحث القفز أم البحث الثنائي أم الخطي؟

المعيار	البحث الخطي	بحث القفز	البحث الثنائي
التعقيد الزمني	O(n)	O(√n)	O(log n)
يتطلب مصفوفة مرتبة؟	لا	نعم	نعم
اتجاه الحركة	للأمام فقط	للأمام ثم قفزة رجوع واحدة	قفزات ذهابًا وإيابًا متكررة
الأفضل عند	بيانات صغيرة أو غير مرتبة	تكلفة الرجوع للخلف عالية	الوصول العشوائي رخيص

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

خطأ شائع يجب تجنّبه

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

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

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

هل يعمل بحث القفز على القوائم المترابطة (Linked Lists)؟ عمليًّا لا يُنصح به، لأنه يعتمد على الوصول المباشر بالفهرس الذي توفّره المصفوفات. في القائمة المترابطة يكلّفك الوصول إلى العنصر رقم k المرور بكل ما قبله، فتضيع فائدة القفز.

ما التعقيد المكاني للخوارزمية؟ O(1) — لا تحتاج ذاكرة إضافية تتناسب مع حجم البيانات، إذ تستخدم عددًا ثابتًا من المتغيرات فقط.

هل يمكن تغيير طول القفزة إلى غير √n؟ يمكن، لكنه يقلّل الكفاءة. أي قيمة أكبر أو أصغر من √n تزيد المجموع n/m + m، والجذر التربيعي هو القيمة المثلى نظريًّا لتحقيق O(√n).