بحث سريع

في علوم الحاسوب ، يشير البحث بالقفز أو البحث بالكتل إلى خوارزمية بحث للقوائم المرتبة . تعمل هذه الخوارزمية عن طريق فحص جميع العناصر L _km أولاً ، حيث${\displaystyle k\in \mathbb {N} }$و m هو حجم الكتلة، حتى يتم العثور على عنصر أكبر من مفتاح البحث . ولإيجاد الموضع الدقيق لمفتاح البحث في القائمة، يتم إجراء بحث خطي على القائمة الفرعية L _{[( k -1) m , km ]} .

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

يمكن تعديل الخوارزمية بإجراء مستويات متعددة من البحث القفزي على القوائم الفرعية، قبل إجراء البحث الخطي النهائي . بالنسبة للبحث القفزي ذي k مستوى، يكون حجم الكتلة الأمثل m l للمستوى l (بدءًا من 1) هو n ( k l)/k . ستُجري الخوارزمية المُعدّلة k قفزة عكسية وتعمل في زمن O( kn  1/( k + 1)) .

خوارزمية JumpSearch تأخذ المدخلات التالية: قائمة مرتبة L ، طولها n ومفتاح البحث s . المخرجات: موضع s في L ، أو لا شيء إذا لم يكن s موجودًا في L.أ ← ٠ ب ← ⌊√ ن ⌋ طالما أن L min( b , n ) - 1 < s ، نفّذ ما يلي: a ← b، b ← b + ⌊√n ⌋ ، إذا كان a ≥ n، فلا تُرجع شيئًا.طالما أن L a < s، قم بما يلي: a ← a + 1 إذا كان a = min( b , n ) ، لا تُرجع شيئًاإذا كانت L a = s، فأرجع a ، وإلا فلا تُرجع شيئًا.

• البحث عن نقطة القفز
• قائمة التخطي
• بحث الاستيفاء
• البحث الخطي - يعمل في زمن O( n )، وينظر فقط إلى الأمام
• البحث الثنائي - يعمل في زمن O(log n )، ويبحث في الاتجاهين الأمامي والخلفي

•  تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "بحث القفز" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .
• بن شنايدرمان ، البحث بالقفز: تقنية بحث تسلسلي سريع ، CACM، 21(10):831-834، أكتوبر 1978.