مقدمة
عثرت على مجموعة من علماء الرياضيات الذين يغنّون ويكتبون الأغاني أيضًا.
لقد ألّفوا أغنية لكل عدد من أعدادهم المفضلة، وكما يمكنك أن تتخيل، لديهم الكثير من الأعداد المفضلة (مثل 0 أو 73 أو 6174).
أنت متشوّق لسماع الأغنية الخاصة بعددك المفضل، لكن مع كل هذه الأغاني التي عليك تصفّحها، قد يستغرق العثور على الأغنية المناسبة بعض الوقت.
لحسن الحظ، رتّبوا أغانيهم في قائمة تشغيل مرتّبة حسب العنوان، وهو ببساطة العدد الذي تدور حوله الأغنية.
تدرك أنه يمكنك استخدام خوارزمية البحث الثنائي للعثور على أغنية بسرعة انطلاقًا من عنوانها.
التعليمات
مهمتك هي تنفيذ خوارزمية البحث الثنائي.
تبحث خوارزمية البحث الثنائي عن عنصر في مصفوفة عبر تقسيمها إلى نصفين مرارًا، مع الاحتفاظ فقط بالنصف الذي يحتوي على العنصر الذي نبحث عنه.
وهي تتيح لنا أن نضيّق بسرعة المواقع المحتملة لعنصرنا حتى نعثر عليه، أو حتى نستبعد كل المواقع المحتملة.
لا يعمل البحث الثنائي إلا عندما تكون المصفوفة مرتبة.
تبدو الخوارزمية هكذا:
- أوجد العنصر الأوسط في مصفوفة مرتبة وقارنه بالعنصر الذي نبحث عنه.
- إذا كان العنصر الأوسط هو عنصرنا، فقد انتهينا!
- إذا كان العنصر الأوسط أكبر من عنصرنا، فيمكننا استبعاد ذلك العنصر وكل العناصر التي بعده.
- إذا كان العنصر الأوسط أصغر من عنصرنا، فيمكننا استبعاد ذلك العنصر وكل العناصر قبله.
- إذا استُبعد كل عنصر في المصفوفة فالعنصر غير موجود فيها.
- وإلا، فأعد العملية على الجزء الذي لم يُستبعد من المصفوفة.
إليك مثالًا:
لنفترض أننا نبحث عن العدد 23 في المصفوفة المرتبة التالية: [4, 8, 12, 16, 23, 28, 32].
- نبدأ بمقارنة 23 بالعنصر الأوسط، وهو 16.
- بما أن 23 أكبر من 16، يمكننا استبعاد النصف الأيسر من المصفوفة، ويتبقى لدينا
[23, 28, 32].
- ثم نقارن 23 بالعنصر الأوسط الجديد، وهو 28.
- بما أن 23 أصغر من 28، يمكننا استبعاد النصف الأيمن من المصفوفة:
[23].
- لقد وجدنا العنصر الذي نبحث عنه.
