البحث الثنائي
| English | العربية |
|---|---|
| sorted/ˈsɔːtɪd/ | مرتبة |
| Binary search/ˈbaɪnəri sɜːtʃ/ | البحث الثنائي |
| target/ˈtɑːɡɪt/ | الهدف |
| middle/ˈmɪdl/ | الوسط |
| comparison/kəmˈpærɪsn/ | مقارنة |
| halves/hɑːvz/ | تنخفض إلى النصف |
| linear search/ˈlɪnɪə sɜːtʃ/ | البحث الخطي |
البحث السريع في قائمة مرتبة
- البحث الثنائي هو طريقة سريعة لإيجاد قيمة هدف في قائمة مرتبة.
- "مرتبة" تعني أن القيم مرتبة — من الأصغر إلى الأكبر، مثلاً.
- هي أسرع بكثير من التحقق من كل عنصر.
- لكن لها شرطاً واحداً صارماً.
البحث الثنائي يحتاج بيانات مرتبة. على قائمة غير مرتبة قد تقفز فوق الهدف وتخطئه. قم بالفرز أولاً دائماً — أو استخدم بحثاً مختلفاً.
يمكن استخدام البحث الثنائي فقط على بيانات:
على البيانات غير المرتبة قد يفتقد الهدف.
تحقق من المنتصف، ثم نصف المسافة
- الفكرة بسيطة: تحقق من العنصر الوسطي. ثم:
- إذا كان الوسطي مساوياً للهدف، لقد وجدته;
- إذا كان الهدف أصغر، ابحث فقط في النصف الأيسر;
- إذا كان الهدف أكبر، ابحث فقط في النصف الأيمن.
البحث الخطي مقابل الثنائي
الثنائي يُضعف النطاق في كل خطوة
البحث الخطي يفحص كل عنصر؛ البحث الثنائي يقسم قائمة مرتبة إلى النصف في كل مقارنة، لذا يحتاج خطوات أقل بكثير.
إذا كان الهدف أكبر من العنصر الأوسط، يبحث البحث الثنائي التالي في:
يجب أن يكون الهدف الأكبر في النصف الأيمن (الأعلى).
كل مقارنة في البحث الثنائي ______ الجزء المتبقي من القائمة.
تقسيم النصف في كل خطوة هو سبب سرعته العالية.
كم عدد فحوصات البحث الثنائي المطلوبة لقائمة مرتبة بحجم 1000 عنصر؟ (2^10 = 1024)
لأن 2^10 = 1024 ≥ 1000، حوالي 10 تقسيمات للنصف تكفي.
لماذا هي سريعة جداً
- كل مقارنة تُنصف الجزء المتبقي من القائمة.
- بالنسبة لـ 1000 عنصر، قد تحتاج عملية البحث الخطي إلى ما يصل إلى 1000 فحص.
- البحث الثنائي يحتاج إلى ما لا يزيد عن 10 تقريباً، لأن $2^{10} = 1024$.
- كلما كانت القائمة أكبر، زادت الميزة النسبية.
يوجد البحث الثنائي 14 في [2,5,8,11,14,17,20] بعد كم مقارنة؟
الوسط 11 → اليمين؛ الوسط 17 → اليسار؛ الوسط 14 → وجد: 3 مقاربات.
على قائمة مرتبة كبيرة، يحتاج البحث الثنائي مقاربات أقل بكثير من البحث الخطي.
تقسيم النصف يتفوق على فحص كل عنصر على حدة.
مقابل البحث الخطي
- يقوم البحث الخطي بفحص كل عنصر على حدة.
- يتفوق البحث الثنائي عليه في القوائم الكبيرة المرتبة عن طريق تنصف القائمة في كل خطوة.
ابحث في [2, 5, 8, 11, 14, 17, 20] عن الرقم 14. العنصر الأوسط هو 11؛ بما أن 14 > 11 → ابحث في النصف الأيمن [14, 17, 20]. العنصر الأوسط هو 17؛ بما أن 14 < 17 → ابحث في [14]. العنصر الأوسط هو 14 — تم العثور عليه بعد 3 مقارنات فقط. كان البحث الخطي سيستغرق 5.
البحث الثنائي يعثر على هدف في قائمة مرتبة بفحص العنصر الأوسط والاحتفاظ بالنصف الذي قد يحتويه فقط. كل مقارنة تُنصف النطاق، لذا فإن 1000 عنصر تحتاج ~10 فحوصات — وهو عدد أقل بكثير من 1000 فحص التي يتطلبها البحث الخطي. يعمل فقط على البيانات المرتبة.