- الهدف
- لا تزال ممكنة
- قيد المقارنة
- مستبعد
- تم العثور عليه
البحث الثنائي
يجد البحث الثنائي قيمةً في قائمة مرتبة بالنظر دائمًا إلى المنتصف. إذا كانت القيمة الوسطى أصغر من اللازم، فالقيمة المطلوبة لا يمكن أن تكون إلا بعدها؛ وإذا كانت أكبر من اللازم، فلا يمكن أن تكون إلا قبلها. وفي الحالتين يُستبعد نصف المتبقي. اختر القيمة التي تبحث عنها، وتقدّم في البحث خطوة بخطوة، وشاهد الجزء المظلل يتقلص حتى تُوجد القيمة المطلوبة أو لا يبقى شيء. اضغط تشغيل لمشاهدة البحث، أو خطوة ورجوع للتقدم خطوةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع. يحدد الخط المتقطع القيمة التي تبحث عنها، والجزء المظلل هو حيث لا يزال من الممكن أن تكون. يحتاج البحث الثنائي إلى قائمة مرتبة، لذا تُرتَّب القائمة غير المرتبة أولًا. اختر القيمة وعدد الأعمدة، أو اكتب أرقامك. عند تحديد اللوحة، تتقدم مفاتيح الأسهم وترجع خطوةً خطوة، ويشغّل مفتاح المسافة البحث ويوقفه مؤقتًا، وينقلك مفتاحا Home وEnd إلى البداية والنهاية.
كيف يعمل
- اختر القيمة التي تبحث عنها وعدد الأعمدة. أو اكتب أرقامك: يرتبها البحث الثنائي أولًا.
- اضغط تشغيل، أو استخدم خطوة ورجوع للتقدم خطوةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع في البحث.
- قارن مربع المقارنات بمربع البحث الخطي يحتاج إلى، لقيمة قرب النهاية أو لقيمة غير موجودة.
كيف يعمل البحث الثنائي
تتبّع الجزء من القائمة المرتبة الذي لا يزال يمكن أن يحتوي القيمة المطلوبة؛ في البداية هو القائمة كلها. انظر إلى القيمة في منتصفه. إذا ساوت القيمة المطلوبة، فقد انتهيت. وإذا كانت أصغر، فالقيمة المطلوبة لا يمكن أن تكون إلا بعدها، فتابع مع الجزء الذي بعد المنتصف. وإذا كانت أكبر، فتابع مع الجزء الذي قبله. وعندما لا يبقى شيء، فالقيمة المطلوبة ليست في القائمة.
لماذا هو سريع جدًا
كل مقارنة تقسم الجزء المتبقي إلى النصف. إذا بدأت بـ n قيمة، يبقى بعد k مقارنة نحو n/2ᵏ على الأكثر، لذا ينتهي البحث بعد ⌊log₂ n⌋ + 1 مقارنة على الأكثر: 6 لـ 40 قيمة، و10 لـ 1000، و20 لمليون. أما البحث الخطي فقد يحتاج إلى النظر في كل قيمة. لكن الشرط أن تكون القائمة مرتبة، وإبقاؤها مرتبة أو ترتيبها أولًا له تكلفته أيضًا.
الأسئلة المتداولة
كيف يعمل البحث الثنائي؟
يقارن القيمة المطلوبة بالقيمة الوسطى في الجزء من القائمة المرتبة الذي لا يزال يمكن أن يحتويها. التساوي يعني أنها وُجدت؛ وإلا يُستبعد النصف الذي لا يمكن أن يحتويها، ويستمر البحث في النصف الآخر حتى تُوجد أو لا يبقى شيء.
كم مقارنة يحتاج البحث الثنائي؟
على الأكثر ⌊log₂ n⌋ + 1 لقائمة من n قيمة: 6 لـ 40، و10 لـ 1000، و20 لمليون. كل مقارنة تقسم المتبقي إلى النصف.
لماذا يحتاج البحث الثنائي إلى قائمة مرتبة؟
لأن مقارنة واحدة لا تخبرك في أي جانب توجد القيمة المطلوبة إلا في قائمة مرتبة. في القائمة غير المرتبة، لا تقول قيمة أصغر في المنتصف شيئًا عن مكان القيمة المطلوبة، فلا يمكن استبعاد شيء.
أي قيمة يجد عند وجود قيم مكررة؟
أيًّا منها، بحسب المواضع التي تقع فيها المنتصفات. والصيغ التي تواصل البحث نحو البداية أو النهاية بعد التطابق تجد أول ظهور أو آخره.
هل تُرسل أرقامي إلى أي مكان؟
لا. يعمل البحث في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر