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

التعليمات

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

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

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

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

إليك مثال:

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

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

السلوك

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

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

اقرأ التوثيق والأمثلة الخاصة بدالة searchsorted لمزيد من التفاصيل:

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

مهام إضافية

• وسّع حلك ليدعم الوسائط المفتاحية by وlt وrev، بحيث يحدد by تحويلًا يُطبَّق على جميع عناصر المصفوفة، ويحدد lt مقارنة، ويحدد rev ما إذا كانت المصفوفة مرتبة بترتيب عكسي. وعند استخدام هذه المعاملات يجب أن تفترض أن المصفوفة قد رُتبت بالفعل باستخدام هذه المعاملات. راجع توثيق sort لمزيد من التفاصيل.
• ادعم المصفوفات التي يتكرر فيها العنصر المستهدف (أي أوجد أول وآخر فهرس لعنصر يساوي العنصر المستهدف).

---

المصدر

ويكيبيديا