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