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

مفهوم خوارزمية البحث الثنائي وكيفية عملها:

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

والفكرة الأساسية من البحث الثنائي هو البحث في مصفوفة مرتبة (في حال لم تكن المصفوفة مرتبة فإننا نقوم بترتيبها)، إذ أن الخوارزمية تقوم بتقسيم فترة البحث إلى النصف، فتأخذ قيمة الموجودة في المنصف، إذا كان القيمة العنصر المراد البحث عنه (key) أقل من قيمة العنصر الموجود في منتصف الفاصل، فإننا نحدد (أو نختار) الفترة الأقل، أي فترة الأعداد ما قبل الـ (key)، أما إذا كان القيمة العنصر المراد البحث عنه (key) أكبر من قيمة العنصر الموجود في منتصف، فإننا نحدد الفترة الأكبر أي فترة الأعداد ما بعد الـ (key)، تستمر بالتحقق بشكل متكرر حتى يتم العثور على القيمة أو أن قيمة العنصر الموجود في منتصف يصبح فارغة.

لنفترض أننا نبحث عن اسم “Smith” في دليل الهاتف، افتح دليل الهاتف إلى منتصفه تقريبًا وانظر إلى الاسم أعلى الصفحة، ماذا هو؟، من المحتمل أنه اسم يبدأ بحرف “M” أو حرف ما قريب منه، فكر الآن في نفسك، هل يأتي “Smith” قبل أو بعد ذلك في دليل الهاتف؟ بعد، أليس كذلك؟، لذا يمكنك تجاهل النصف الأول من دليل الهاتف بالكامل، الآن افتح النصف المتبقي إلى منتصفه تقريبًا مرة أخرى، من المحتمل أنك في مكان ما بالقرب من “T”، هل يأتي “Smith” قبل أو بعد حرف “T” في دليل الهاتف؟ قبل، لذا يمكنك تجاهل النصف الأخير. استمر في القيام بذلك حتى تجد الاسم الذي تبحث عنه.

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

تعقيد الوقت لخوارزمية البحث الثنائي:

التعقيد الوقت لخوارزمية البحث الثنائي هو “O(log n)”، سيكون التعقيد الوقت الأفضل في الحالة (best case) هو “(O(1″، يكون عندما تتطابق قيمة المؤشر (index) مباشرة مع القيمة المطلوبة، قد يكون السيناريو الأسوأ هو أن القيمة العنصر المراد البحث عنه موجودة في أي من طرفي القائمة أو أنها غير موجودة في القائمة.

الفرق بين خوارزمية البحث الثنائي و خوارزمية البحث الخطي:

خوارزمية البحث الثنائي أسرع بكثير من خوارزمية البحث الخطي لمعظم مجموعات البيانات، إذا نظرنا إلى كل عنصر بالترتيب، فقد نضطر إلى إلقاء نظرة على كل عنصر في مجموعة البيانات قبل العثور على العنصر الذي تبحث عنه، لكن مع استخدام خوارزمية البحث الثنائي، يمكنك التخلص من نصف البيانات في كل مرة. إذا كان (n) هو عدد العناصر، فعندئذٍ بعد القرار الأول، يمكنك حذف (n / 2) منها، بعد القرار الثاني، واستبعدت (3n/4) منهم. بعد القرار الثالث قمت بإلغاء (7n /8) منهم، بمعنى آخر، البحث الثنائي هو “O(logn)”. يمكنك أن ترى أنه بالنسبة لمجموعة البيانات الكبيرة، سيكون البحث الثنائي أفضل بكثير من البحث الخطي.

لكن هناك حالة سيكون فيها البحث الخطي أسرع من البحث الثنائي، وهي إذا كان العنصر الذي يتم البحث عنه هو العنصر الأول في القائمة، فسيجده البحث الخطي في أول تكرار له سيكون تعقيد الوقت في هذه الحالة “O(1)”، بينما سيأخذ البحث الثنائي أقصى عدد من عمليات البحث سيكون تعقيد الوقت في هذه الحالة “O(log n)” .

كود الخوارزمية باستخدام لغة ++C:

هناك طريقتان لتنفيذه:

• طريقة الحلقات التكرارية (loop).

• طريقة الاستدعاء الذاتي (recursion).

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

ذهب راشد للقتال في الحرب. كان هناك (N) عدد جنود بقوى مختلفة، وستكون هناك (Q) عدد الجولات للقتال، وفي كل جولة ستكون القوة (M) لراشد مختلفة عن الجولات الأخرى، حيث أن باستخدام قوته يمكن لـراشد قتل جميع الجنود الذين تكون قوتهم أقل من أو تساوي قوته، بعد كل جولة، سوف سيرجع جميع الجنود الذين ماتوا في الجولة السابقة للحياة من جديد، بحيث يكون هناك (N) جنود للقتال في كل جولة. نظرًا لأن راشد ضعيف في الرياضيات، ساعده في حساب عدد الجنود الذين يمكنه قتلهم في كل جولة ومجموع الإجمالي لقوات الجنود الذين استطاع قتلهم.

المدخلات:

السطر الأول يحتوي عدد صحيح هو (N) عدد جنود، حيث (N<= 10000)، السطر الثاني يحتوي على (N) من الأعداد الصحيحة وهي قوة كل جندي حيث أن (قوة كل جندي <= 100)، السطر الثالث عدد الصحيح (Q) عدد جولات القتال، الأسطر التي تليها هي قوة راشد في كل جولة، حيث أن (M<= 100).

المخرجات:

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

مثال:

المدخلات:

7
1 2 3 4 5 6 7
3
3
10
2

المخرجات:

6 3
28 7
3 2

الحل: (مقترح)