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

التعليمات

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

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

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

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

إليك مثال:

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

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

القيود

توفر Rust بالفعل في مكتبتها القياسية دالة البحث الثنائي. في هذا التمرين، لا ينبغي أن تستخدم هذه الدالة، بل استخدم أدوات أساسية أخرى بدلًا منها.

للحصول على نقاط إضافية

هل جعلت الاختبارات تنجح والكود نظيفًا؟ إذا أردت، فهناك بعض الأمور الإضافية التي يمكنك تجربتها.

• حاليًا، من المحتمل أن دالة find لديك تعمل فقط مع شرائح من الأعداد، لكن نظام الأنواع في Rust مرن بما يكفي لإنشاء دالة find تعمل على كل الشرائح التي تحتوي على عناصر يمكن ترتيبها.
• بالإضافة إلى ذلك، يمكن لدالة find هذه أن تعمل ليس فقط على الشرائح، بل في الوقت نفسه أيضًا على Vec أو Array.

لتشغيل اختبارات النقاط الإضافية، أزل علامة #[ignore] ونفّذ الاختبارات مع ميزة generic، هكذا:

$ cargo test --features generic

ثم شاركنا أفكارك في تعليق على الحل المُرسَل. هل جعلت هذه التجربة الكود أفضل؟ أسوأ؟ هل تعلمت منها شيئًا؟

---

المصدر

ويكيبيديا