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

التعليمات

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

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

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

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

إليك مثال:

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

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

رسائل الاستثناء

أحيانًا تحتاج إلى رفع استثناء. وعندما تفعل ذلك، ينبغي أن تُضمّن دائمًا رسالة خطأ ذات معنى تشير إلى مصدر الخطأ. فهذا يجعل الكود أكثر وضوحًا ويساعد كثيرًا في تصحيح الأخطاء. وفي الحالات التي تعرف فيها أن مصدر الخطأ سيكون من نوع معيّن، يمكنك اختيار رفع أحد أنواع الأخطاء المدمجة، لكن يجب أن تُضمّن معه رسالة ذات معنى.

يتطلب هذا التمرين تحديدًا أن تستخدم جملة raise لـ"رمي" ValueError عندما لا تكون القيمة المعطاة موجودة داخل المصفوفة. ولن تنجح الاختبارات إلا إذا نفّذت raise على الاستثناء وأدرجت معه رسالة.

لرفع ValueError مصحوبًا برسالة، اكتب الرسالة كوسيط لنوع exception:

# example when value is not found in the array.
raise ValueError("value not in array")

---

المصدر

ويكيبيديا