خوارزمية البحث الثنائي – Binary Search

لقد تحدثنا في المقال السابق عن خوارزمية البحث الخطي، وذكرنا أنّ درجة تعقيد الخوارزمية من المرتبة O(n) أي تعقيد خطي. لكن ماذا لو كان عدد العناصر التي يجب البحث ضمنها كبيرًا؟ سيكون تعقيد الخوارزمية كبيرًا! وماذا لو أنّ العناصر مرتبةٌ ضمن مصفوفة البحث؟ ألا يجب أن نستغل هذه الميزة لتحسين البحث؟!

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

خوارزمية البحث الثنائي هي خوارزمية بحثٍ تعمل على مبدأ فرّق تَـسُد! بحيث تكون عناصر مصفوفة البحث مرتبةٌ ترتيبًا تصاعديًا أو تنازليًا، وإن لم تكن مرتبةً يجب أن نقوم بترتيبها بطريقةٍ ما،  فلنرَ كيف تعمل!

خوارزمية البحث الخطي – Linear Search

لفهم مدى فعالية الخوارزمية، دعونا نتخيل لو تمّ ترتيب جميع الأسماء الموجودة في العالم بترتيبٍ أبجدي، وقمنا بالبحث عن اسمٍ معينٍ موجود بين هذه الأسماء، ستقوم هذه الخوارزمية بإيجاد موقع الاسم فقط ضمن 35 عملية بحثٍ على الأكثر.

ما هي آلية عمل الخوارزمية؟

تبدأ الخوارزمية بتحديد دليل العنصر الذي يقع في وسط المصفوفة حتى تقسم المصفوفة إلى قسمين (هنا يتبيّن مبدأ فرق تسد).

مثال عملي لتوضيح آلية العمل:

فلنفترض وجود مصفوفة (Arr) تحتوي على الأعداد من صفر إلى 9:

enter image description here

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

لكن إنْ استخدمنا خوارزمية البحث الثنائي سيتم إنجاز المطلوب خلال وقت أسرع وزمن تعقيد أقل، فلنختبر الخوارزمية عن طريق البحث عن الرقم 3 على سبيل المثال:

علينا بدايةً تحديد موقع (دليل) العنصرين الأول والأخير في المصفوفة على النحو الآتي:

Low = 0

High = n-1

بعدها نقوم بحساب دليل العنصر الذي يقع في منتصف المصفوفة وليكن mid وذلك عن طريق جمع Low و High وتقسيم الناتج على 2:

enter image description here

ونتحقق من أنّ العنصر الذي دليله mid أكبر أم أصغر من القيمة التي نبحث عنها، وبما أننا نعمل دومًا على أعداد مرتبة، لذلك إذا كان العنصر الذي دليله mid أصغر سنقوم بتغيير قيمة الـدليل Low إلى الـ (mid+1) أو إذا كانت أكبر سنقوم بتغيير قيمة الـدليل High إلى (mid-1)، إذْ أننا في كل مرةٍ نقوم بتقسيم المصفوفة إلى قسمين، والبحث في القسم الذي نكون متأكدين من وجود العدد الذي نبحث عنه فيه.

طبعا نزيد أو ننقص واحد من القيمة بسبب وجود شرطٍ آخر، هو أنه لو كانت القيمة متساوية نقوم بطباعة الرقم، غير ذلك نحن لسنا بحاجة لموقع الـ high أو الـ Low الأصلي لأنه ليس مطابقًا للقيمة التي نبحث عنها.

مثال برمجي لتوضيح الخطوات:

زمن تعقيد الخوارزمية (Time Complexity)

الزمن اللوغاريتمي هو اللوغاريتم الثنائي للعدد Log(n)، وذلك لأنه في كل مرةٍ نقوم بتقسيم مجال البحث إلى قسمين.

 

  • إعداد: صامد الحجاجلة
  • مراجعة: نور عبدو
  • تدقيق لغوي: مروى بوسطه جي
تعليقات
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More