البحث بالقفز
البحث بالقفز يشبه طريقتك في البحث عن صفحة في كتاب بلا فهرس: تقلب إلى الأمام رزمة من الصفحات في كل مرة وتلقي نظرة على أرقام الصفحات، وحين تتجاوز الصفحة تعود صفحةً صفحة في الرزمة الأخيرة. وفي قائمة مرتبة يحتاج إلى مقارنات أقل بكثير من فحص كل قيمة.
الفكرة
في قائمة مرتبة، تخبرك آخر قيمة في كتلة هل يمكن أن يكون الهدف فيها أصلًا: إن كانت أصغر من الهدف، فكل قيمة في الكتلة أصغر منه أيضًا. لذا لا حاجة إلى النظر داخلها. افحص آخر قيمة في كل كتلة بالترتيب، متخطيًا كتلًا كاملة، حتى تجد واحدة ليست أصغر من الهدف. عندها لا يمكن أن يكون الهدف إلا في تلك الكتلة: امسحها من بدايتها.
مثال
ابحث عن 23 في 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 بكتل من 3. تنتهي الكتلة الأولى بـ 8، وهي أصغر، فتخطَّها. وتنتهي الكتلة الثانية بـ 23، وهي ليست أصغر، فلا يمكن أن تكون 23 إلا في 12, 16, 23. مسحها يعطي 12 ثم 16 ثم 23: وُجدت بعد 5 مقارنات، بينما يحتاج البحث الخطي إلى 6 والبحث الثنائي إلى 3. وعند البحث عن 40، تقود نهايات الكتل 8 و23 و72 إلى الكتلة 38, 56, 72؛ 38 أصغر و56 أكبر بالفعل، فـ 40 ليست فيها: 5 مقارنات مرة أخرى.
لماذا √n
مع كتل من m قيمة، يتطلب العثور على الكتلة الصحيحة نحو n/m مقارنة على الأكثر، ومسحها m على الأكثر. القفزات القليلة الطويلة تجعل المسح طويلًا، والقفزات الكثيرة القصيرة تجعل القفز طويلًا. يكون المجموع n/m + m أصغر ما يمكن حين يتساوى الجزآن، عند m = √n، حيث يبلغ نحو 2√n. مع 40 قيمة يعني ذلك كتلًا من 6 و13 مقارنة على الأكثر، ومع مليون قيمة كتلًا من 1,000 ونحو 2,000 مقارنة.
أين يناسب
يحتاج البحث الثنائي إلى مقارنات أقل، نحو log₂ n. لكن البحث الثنائي يقفز ذهابًا وإيابًا في أنحاء القائمة كلها، بينما يتقدم البحث بالقفز إلى الأمام فقط ويرجع مرة واحدة، إلى بداية كتلة واحدة. وهذا جعله جذابًا للبيانات المخزنة على شريط أو في بنية مترابطة يكون الرجوع فيها بطيئًا. وصفه Ben Shneiderman باسم jump searching عام 1978. والفكرة نفسها، أي التقسيم إلى √n كتلة، وتُسمى غالبًا تفكيك الجذر التربيعي، تظهر في خوارزميات أخرى كثيرة.
جرّبه
افتح التطبيق، واختر قيمة في ابحث عن، واضغط خطوة. تُبرز كل قفزة آخر قيمة في كتلة؛ وتبهت الكتل المتخطاة، وتُظلَّل الكتلة التي قد تحتوي على الهدف أثناء مسحها. غيّر حجم القفزة من √n إلى 2 أو 8 مع 40 عمودًا، وشاهد كيف يتغير التوازن بين القفز والمسح.
الأسئلة المتداولة
ما التعقيد الزمني للبحث بالقفز؟
O(√n) مع كتل من √n قيمة: نحو 2√n مقارنة على الأكثر. ويحتاج إلى ذاكرة إضافية O(1) وإلى قائمة مرتبة.
ما الفرق بين البحث بالقفز والبحث الثنائي؟
البحث الثنائي ينصّف الجزء المتبقي في كل مرة ويحتاج إلى نحو log₂ n مقارنة، لكنه يتحرك ذهابًا وإيابًا. أما البحث بالقفز فيتخطى إلى الأمام بخطوات ثابتة ويمسح كتلة واحدة، ويحتاج إلى نحو 2√n مقارنة، ولا يرجع إلا مرة واحدة.
هل يمكن استخدام البحث الثنائي بدل المسح في الكتلة الأخيرة؟
نعم. البحث في الكتلة بالبحث الثنائي يقلّص المسح من m مقارنة إلى نحو log₂ m. أما القفزات فتظل تكلّف n/m، لذا تصبح الكتل الأكبر أجدى حينها.
هل يحتاج البحث بالقفز إلى قائمة مرتبة؟
نعم. تخطّي كتلة آمن فقط لأن كون آخر قيمة فيها أصغر يعني أن كل قيمة فيها أصغر. ويرتب التطبيق القائمة غير المرتبة أولًا.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب البحث بالقفز