خوارزمية البحث الثنائية مع مثال

قبل أن نتعلم البحث الثنائي، دعونا نتعرف على ماهية البحث.

ما هو البحث؟

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

ما هو البحث الثنائي؟

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

كيف يعمل البحث الثنائي؟

تعمل عملية البحث الثنائي بالطريقة التالية:

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

خوارزمية البحث الثنائي (الرمز الزائف)

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

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

تُعيد الدالة فهرس الهدف عند النجاح، و-1 عند عدم وجود القيمة. ولأن النطاق يتقلص إلى النصف في كل دورة، فإن الحلقة تُنفذ على الأكثر log₂(n) مرة.

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

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

الصورة أعلاه توضح ما يلي:

1. لديك مصفوفة مكونة من 10 أرقام، ويجب العثور على العنصر 59.
2. جميع العناصر مُرقمة من 0 إلى 9. الآن، يتم حساب منتصف المصفوفة. وللقيام بذلك، نأخذ أقصى قيمتي الفهرس من اليسار واليمين ونقسمهما على 2. والنتيجة هي 4.5، ولكننا نأخذ أقرب عدد صحيح للأسفل. لذا فإن المنتصف هو 4.
3. تقوم الخوارزمية بإسقاط جميع العناصر من المنتصف (4) إلى الحد الأدنى، لأن 59 أكبر من 24، والآن لم يتبق من المصفوفة سوى 5 عناصر فقط.
4. الآن، 59 أكبر من 45 وأصغر من 63. والوسط هو 7. وبالتالي تصبح قيمة الفهرس الأيمن هي الوسط - 1، والتي تساوي 6، وتبقى قيمة الفهرس الأيسر كما هي من قبل، وهي 5.
5. عند هذه النقطة، تعلم أن 59 يأتي بعد 45. وبالتالي، يصبح المؤشر الأيسر، وهو 5، في المنتصف أيضًا.
6. تستمر هذه التكرارات حتى يتم تقليل المصفوفة إلى عنصر واحد فقط، أو يصبح العنصر الذي سيتم العثور عليه في منتصف المصفوفة.

مثال 2

دعونا نلقي نظرة على المثال التالي لفهم آلية عمل البحث الثنائي.

1. لديك مصفوفة من القيم المصنفة تتراوح من 2 إلى 20 وتحتاج إلى تحديد موقع 18.
2. متوسط ​​الحدين الأدنى والأعلى هو (l + r) / 2 = 4. القيمة التي يتم البحث عنها أكبر من المنتصف، وهو 4.
3. يتم استبعاد قيم المصفوفة الأقل من القيمة الوسطى من البحث، ويتم البحث عن القيم الأكبر من القيمة الوسطى 4.
4. هذه عملية تقسيم متكررة حتى يتم العثور على العنصر الفعلي المطلوب البحث عنه.

لماذا نحتاج إلى البحث الثنائي؟

الأسباب التالية تجعل البحث الثنائي خيارًا أفضل لاستخدامه كخوارزمية بحث:

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

تعرّف على الدرس التعليمي التالي حول البحث الخطي: Python, C++ مثال.

البحث الثنائي مقابل البحث الخطي

يُعدّ البحث الثنائي والبحث الخطي من أكثر الطرق شيوعًا للعثور على قيمة في مجموعة بيانات. يوضح الجدول أدناه أوجه الاختلاف بينهما:

باختصار، البحث الثنائي أسرع بكثير على البيانات الكبيرة المصنفة، بينما البحث الخطي أبسط وهو الخيار الوحيد عندما لا تكون البيانات مصنفة.

الأسئلة الشائعة