المقارنات
لا تزال ممكنة
البحث الثنائي يحتاج إلى

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

مزيد عن البحث الأسي

البحث الأسي

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

كيف يعمل

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

كيف يعمل البحث الأسي

انظر إلى القيمة في الموضع 1. إن كانت أصغر من الهدف، فانظر إلى الموضع 2، ثم 4, 8, 16، مضاعفًا في كل مرة. وما إن تجد قيمة ليست أصغر حتى تتوقف: لا يمكن أن يكون الهدف إلا بعد الموضع السابق الذي نظرت إليه وقبل هذا الموضع. طبّق البحث الثنائي على هذا النطاق. وإذا تجاوزت المضاعفة نهاية القائمة، فطبّق البحث الثنائي من آخر موضع نظرت إليه حتى النهاية.

سريع قرب البداية، ولا حاجة إلى الطول

للوصول إلى هدف في الموضع i، تحتاج المضاعفة إلى نحو log₂ i نظرة، والنطاق الذي تجده يضم أقل من i قيمة، لذا يحتاج البحث الثنائي إلى نحو log₂ i أخرى. أي نحو 2 log₂ i إجمالًا، وهذا يعتمد على موضع الهدف لا على طول القائمة. تُوجد الأهداف القريبة من البداية أسرع مما في البحث الثنائي العادي، أما الأهداف القريبة من النهاية فتكلّف حتى نحو الضعف. ولأنه لا يحتاج أبدًا إلى طول القائمة، فهو يعمل أيضًا على القوائم الأطول من أن تُقاس أو التي لا نهاية معروفة لها.

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

كيف يعمل البحث الأسي؟

في قائمة مرتبة يفحص المواضع 1, 2, 4, 8 وهكذا حتى لا تكون القيمة هناك أصغر من الهدف. عندها لا يمكن أن يكون الهدف إلا بين آخر موضعين فُحصا، ويجده البحث الثنائي في ذلك النطاق.

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

عندما يكون الهدف قرب بداية القائمة، نعم: يحتاج إلى نحو 2 log₂ i مقارنة لهدف في الموضع i، مهما كان طول القائمة. وعندما يكون الهدف قرب النهاية، يكون البحث الثنائي العادي أسرع، بما يصل إلى نحو الضعف.

فيمَ يُستخدم؟

في البحث في قوائم طولها مجهول أو غير محدود، مثل تدفق بيانات أو متتالية لا نهائية، وفي دمج المقاطع المرتبة، حيث يكون التطابق التالي قريبًا عادةً. ويستخدم وضع الركض (galloping) في Timsort فكرة المضاعفة نفسها.

لماذا يُسمى أسيًا؟

لأن المواضع التي يفحصها تنمو نموًا أسيًا: 1, 2, 4, 8, 16، كل منها ضعف الذي قبله. ويُسمى أيضًا البحث بالمضاعفة أو بحث الركض.

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

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

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

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

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