المقارنات
حجم القفزة
البحث الخطي يحتاج إلى

  • الهدف
  • الكتلة الحالية
  • قيد المقارنة
  • مستبعد
  • تم العثور عليه

مزيد عن البحث بالقفز

البحث بالقفز

يقع البحث بالقفز بين البحث الخطي والبحث الثنائي. فهو يتقدم في قائمة مرتبة بقفزات من m موضع، ولا يفحص إلا آخر قيمة في كل كتلة، حتى يصل إلى كتلة آخر قيمة فيها ليست أصغر من الهدف. ثم يمسح تلك الكتلة من بدايتها. اختر القيمة وحجم القفزة، وشاهد كم مقارنة تحتاج القفزات والمسح. اضغط تشغيل لمشاهدة البحث، أو خطوة ورجوع للتقدم مقارنةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع. يحدد الخط المتقطع القيمة التي تبحث عنها، والجزء المظلل هو الكتلة الحالية. يحتاج البحث بالقفز إلى قائمة مرتبة، لذا تُرتَّب القائمة غير المرتبة أولًا. اختر القيمة، وحجم القفزة، وعدد الأعمدة، أو اكتب أرقامك. عند تحديد اللوحة، تتقدم مفاتيح الأسهم وترجع خطوةً خطوة، ويشغّل مفتاح المسافة البحث ويوقفه مؤقتًا، وينقلك مفتاحا Home وEnd إلى البداية والنهاية.

كيف يعمل

  1. اختر القيمة التي تبحث عنها، وحجم القفزة، وعدد الأعمدة. أو اكتب أرقامك: سيرتبها البحث بالقفز أولًا.
  2. اضغط تشغيل، أو استخدم خطوة ورجوع للتقدم مقارنةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع في البحث.
  3. جرّب حجم قفزة 2 ثم 8 على 40 عمودًا، وقارن عدد المقارنات بما يحدث مع √n.

كيف يعمل البحث بالقفز

قسّم القائمة المرتبة إلى كتل من m قيمة. انظر إلى آخر قيمة في الكتلة الأولى. إن كانت أصغر من الهدف، فلا يمكن أن يكون الهدف في أي مكان من تلك الكتلة، فاقفز إلى نهاية الكتلة التالية وانظر مجددًا. وما إن تكون آخر قيمة في كتلة ليست أصغر، فلا يمكن أن يكون الهدف إلا في تلك الكتلة: ارجع إلى بدايتها وافحص قيمها واحدة تلو الأخرى حتى تجد الهدف أو تتجاوزه.

اختيار حجم القفزة

مع n قيمة، تحتاج القفزات إلى n/m مقارنة على الأكثر، والمسح إلى m على الأكثر. القفزات الصغيرة تجعل المسح قصيرًا لكن القفزات كثيرة، والقفزات الكبيرة تفعل العكس. يكون المجموع n/m + m أصغر ما يمكن عند m = √n، وهذا يعطي نحو 2√n مقارنة: 13 على الأكثر لـ 40 قيمة، مقابل 40 للبحث الخطي و6 للبحث الثنائي. لا يرجع البحث بالقفز أبدًا أكثر من كتلة واحدة، وهذا يفيد حين يكون التحرك إلى الخلف في البيانات بطيئًا.

الأسئلة المتداولة

كيف يعمل البحث بالقفز؟

في قائمة مرتبة، يقفز إلى الأمام بخطوات من m موضع ويفحص آخر قيمة في كل كتلة. وحين لا تعود تلك القيمة أصغر من الهدف، لا يمكن أن يكون الهدف إلا في تلك الكتلة، فيمسحها من بدايتها.

ما أفضل حجم للقفزة؟

√n، مقرّبًا. تكلّف القفزات حتى n/m مقارنة والمسح حتى m، ويكون مجموعهما أصغر ما يمكن حين يتساويان، عند m = √n. وهذا يعطي نحو 2√n مقارنة في أسوأ حالة.

هل البحث بالقفز أسرع من البحث الثنائي؟

لا، يحتاج البحث الثنائي إلى مقارنات أقل: نحو log₂ n مقابل نحو 2√n. ومع ذلك قد يتفوق البحث بالقفز حين يكون الرجوع في البيانات مكلفًا، لأنه لا يرجع إلا مرة واحدة، إلى بداية كتلة واحدة.

أي تطابق يجده عند تكرار القيم؟

الأول. كل كتلة يتخطاها تنتهي بقيمة أصغر من الهدف، فلا يمكن لأي كتلة سابقة أن تحتوي على تطابق، والمسح يبدأ من بداية الكتلة.

هل تُرسل أرقامي إلى أي مكان؟

لا. يعمل البحث في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر