البحث الثنائي

التعليمات

مهمتك هي تنفيذ خوارزمية بحث ثنائي.

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

تبدو الخوارزمية هكذا:

• ابحث عن العنصر الأوسط في مصفوفة مرتبة وقارنه بالعنصر الذي نبحث عنه.
• إذا كان العنصر الأوسط هو عنصرنا، فقد انتهينا!
• إذا كان العنصر الأوسط أكبر من عنصرنا، يمكننا استبعاد ذلك العنصر وجميع العناصر التي بعده.
• إذا كان العنصر الأوسط أصغر من عنصرنا، يمكننا استبعاد ذلك العنصر وجميع العناصر التي قبله.
• إذا استُبعد كل عنصر في المصفوفة، فإن العنصر غير موجود فيها.
• وإلا، فأعد العملية على الجزء الذي لم يُستبعد من المصفوفة.

إليك مثال:

لنفترض أننا نبحث عن العدد 23 في المصفوفة المرتبة التالية: [4, 8, 12, 16, 23, 28, 32].

• نبدأ بمقارنة 23 بالعنصر الأوسط، 16.
• بما أن 23 أكبر من 16، يمكننا استبعاد النصف الأيسر من المصفوفة، ويتبقى لدينا [23, 28, 32].
• ثم نقارن 23 بالعنصر الأوسط الجديد، 28.
• بما أن 23 أصغر من 28، يمكننا استبعاد النصف الأيمن من المصفوفة: [23].
• لقد وجدنا العنصر.

القيود

لا تبخس نفسك حقّها بالاستعانة بالمكتبة القياسية لأدوات المجموعات. يمكنك إكمال هذا التمرين دون أدوات مثل Array.tryFindIndex، بل ينبغي لك ذلك.

تلميحات

في هذا التمرين تفيدك ميزات F# التالية:

• الاستدعاء الذَّيلي تجنّب تجاوز سعة المكدّس مع المدخلات الكبيرة باستخدام الاستدعاء الذَّيلي. ومع أنه لا توجد حالات اختبار تتحقق من ذلك صراحةً، فإن استخدام الاستدعاء الذَّيلي يؤدي إلى حل أسرع أداءً. ومن المصادر الجيدة الأخرى عن الاستدعاء الذَّيلي هذا المنشور.
• مطابقة الأنماط قوية للغاية وتساعد على تبسيط المنطق الشرطي متعدد الفروع.

---

المصدر

ويكيبيديا