- الهدف
- لا تزال ممكنة
- قيد المقارنة
- مستبعد
- تم العثور عليه
البحث بالاستيفاء
البحث بالاستيفاء يجد قيمةً في قائمة مرتبة بالطريقة التي تفتح بها دليل الهاتف: لاسم يبدأ بحرف الياء تفتح الدليل قرب النهاية، لا في المنتصف. فهو يقدّر موضع الهدف من القيمتين عند طرفي الجزء المتبقي. اختر القيمة وطريقة توزيع القيم، وتقدّم عبر الفحوص واحدًا تلو الآخر، وانظر متى يتفوق التقدير على البحث الثنائي ومتى لا يتفوق. اضغط تشغيل لمشاهدة البحث، أو خطوة ورجوع للتقدم خطوةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع. يحدد الخط المتقطع القيمة التي تبحث عنها، والجزء المظلل هو حيث لا يزال يمكن أن تكون. يحتاج البحث بالاستيفاء إلى قائمة مرتبة، لذا تُرتَّب القائمة غير المرتبة أولًا. اختر القيمة، وطريقة توزيع القيم، وعدد الأعمدة، أو اكتب أرقامك. عند تحديد اللوحة، تتقدم مفاتيح الأسهم وترجع خطوةً خطوة، ويشغّل مفتاح المسافة البحث ويوقفه مؤقتًا، وينقلك مفتاحا Home وEnd إلى البداية والنهاية.
كيف يعمل
- اختر القيمة التي تبحث عنها، وطريقة توزيع القيم، وعدد الأعمدة. أو اكتب أرقامك: يرتّبها البحث بالاستيفاء أولًا.
- اضغط تشغيل، أو استخدم خطوة ورجوع للتقدم خطوةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع في البحث.
- بدّل «التوزيع» بين «متساوٍ» و«فجوات عشوائية» و«منحاز»، وقارن «الفحوص» بـ«البحث الثنائي يحتاج إلى».
كيف يعمل البحث بالاستيفاء
انظر إلى أول قيمة وآخر قيمة في الجزء من القائمة المرتبة الذي لا يزال يمكن أن يحتوي على الهدف. إذا كان الهدف يقع مثلًا على بُعد 40% من المسافة بين أول قيمة وآخرها، فافحص الموضع الذي يقع على بُعد 40% من طول هذا الجزء. إذا كانت القيمة هناك هي الهدف، فقد انتهيت. وإذا كانت أصغر، تبقى المواضع التي بعدها فقط؛ وإذا كانت أكبر، تبقى المواضع التي قبلها فقط. قدّر من جديد فيما تبقى. وإذا كان الهدف أصغر من أول قيمة أو أكبر من آخر قيمة، فهو ليس في القائمة.
متى ينجح التقدير
إذا كانت القيم موزعة بالتساوي، مثل 10, 20, 30 وهكذا، يقع التقدير الأول على الهدف أو قريبًا جدًا منه، ويحتاج البحث في المتوسط إلى نحو log₂(log₂ n) فحص: نحو 5 لمليار قيمة، مقابل 30 للبحث الثنائي. وإذا تكدست القيم، مثل 1, 2, 3, 4, 1000، تظل التقديرات تقع في المكان الخطأ وقد لا يستبعد كل فحص إلا قيمة واحدة، لذا فأسوأ حالة هي n فحص. أما البحث الثنائي فلا يتجاوز أبدًا نحو log₂ n.
الأسئلة المتداولة
كيف يعمل البحث بالاستيفاء؟
في قائمة مرتبة، يقدّر موضع الهدف من أول قيمة وآخر قيمة في الجزء المتبقي، ثم يفحص ذلك الموضع، ويحتفظ فقط بالجزء الذي في الجهة الصحيحة. إنه مثل البحث الثنائي، لكن بتخمين أذكى من المنتصف.
هل البحث بالاستيفاء أسرع من البحث الثنائي؟
مع القيم الموزعة بالتساوي، نعم: نحو log₂(log₂ n) فحص في المتوسط بدلًا من نحو log₂ n. ومع القيم الموزعة بغير تساوٍ قد يكون أبطأ بكثير، حتى n فحص، بينما لا يحتاج البحث الثنائي أبدًا إلى أكثر من نحو log₂ n.
لماذا قد يكون بطيئًا؟
لأن التقدير يفترض أن القيم تزداد بالتساوي. فإذا كانت معظم القيم صغيرة وبعضها ضخمًا جدًا، يقع تقدير الهدف الصغير قرب البداية مرة بعد مرة، ولا يستبعد في كل مرة إلا قيمة أو قيمتين.
أين يُستخدم البحث بالاستيفاء؟
حيث تكون المفاتيح موزعة بالتساوي تقريبًا ويكون الفحص مكلفًا، مثل البحث عن السجلات بمعرّف رقمي أو بقيمة تجزئة على القرص. وتجمع أنظمة كثيرة بينه وبين البحث الثنائي لتبقى أسوأ حالة جيدة.
هل تُرسل أرقامي إلى أي مكان؟
لا. يعمل البحث في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر