مقدمة
في علم الحاسوب، البحث الثنائي، المعروف أيضًا باسم بحث الفاصل الزمني النصفي، أو البحث اللوغاريتمي، أو القطع الثنائي، هو خوارزمية بحث تجد موضع قيمة مستهدفة داخل مصفوفة مرتبة. يقارن البحث الثنائي القيمة المستهدفة بالعنصر الأوسط من المصفوفة. إذا لم تكن متساوية، يتم التخلص من النصف الذي لا يمكن أن تقع فيه القيمة المستهدفة، ويستمر البحث في النصف المتبقي، مع الأخذ في الاعتبار مرة أخرى العنصر الأوسط للمقارنة مع القيمة المستهدفة، ويكرر هذا حتى يتم العثور على القيمة المستهدفة. إذا انتهى البحث بالنصف المتبقي فارغًا، فهذا يعني أن الهدف ليس في المصفوفة.
يعتبر البحث الثنائي أحد أكثر الخوارزميات الأساسية في علم الحاسوب. يرجع ذلك إلى كفاءته العالية وسهولة تنفيذه. يستخدم البحث الثنائي على نطاق واسع في مجموعة متنوعة من التطبيقات، بما في ذلك قواعد البيانات، ومحركات البحث، وخوارزميات الضغط.
آلية عمل البحث الثنائي
لفهم آلية عمل البحث الثنائي، تخيل أن لديك قائمة مرتبة من الأرقام وتريد العثور على رقم معين داخل هذه القائمة. الطريقة التقليدية للبحث هي المرور على كل رقم في القائمة واحدًا تلو الآخر حتى تجد الرقم المطلوب. هذه الطريقة تسمى “البحث الخطي” وهي غير فعالة خاصة إذا كانت القائمة طويلة جدًا.
البحث الثنائي يقدم طريقة أكثر ذكاءً. بدلاً من البحث بشكل تسلسلي، فإنه يقسم القائمة إلى نصفين في كل مرة. وإليك الخطوات:
- ابحث عن العنصر الأوسط: ابدأ بتحديد العنصر الموجود في منتصف القائمة.
- قارن: قارن العنصر الأوسط بالرقم الذي تبحث عنه.
- التخلص من النصف غير الضروري:
- إذا كان الرقم الذي تبحث عنه هو نفسه العنصر الأوسط، فقد وجدته!
- إذا كان الرقم الذي تبحث عنه أصغر من العنصر الأوسط، فهذا يعني أنه يجب أن يكون موجودًا في النصف الأول من القائمة. يمكنك الآن تجاهل النصف الثاني من القائمة والتركيز على النصف الأول فقط.
- إذا كان الرقم الذي تبحث عنه أكبر من العنصر الأوسط، فهذا يعني أنه يجب أن يكون موجودًا في النصف الثاني من القائمة. يمكنك الآن تجاهل النصف الأول من القائمة والتركيز على النصف الثاني فقط.
- كرر العملية: كرر الخطوات من 1 إلى 3 على النصف المتبقي من القائمة. استمر في تقسيم النصف المتبقي إلى نصفين حتى تجد الرقم الذي تبحث عنه أو تصل إلى قائمة فارغة (في هذه الحالة، الرقم غير موجود في القائمة).
مثال:
لنفترض أن لدينا القائمة المرتبة التالية: [2, 5, 7, 8, 11, 12]
ونريد البحث عن الرقم 11.
- العنصر الأوسط هو 7.
- 11 أكبر من 7، لذلك نتجاهل النصف الأول من القائمة ونركز على النصف الثاني: [8, 11, 12].
- العنصر الأوسط في النصف الثاني هو 11.
- 11 يساوي 11، لذلك وجدنا الرقم الذي نبحث عنه!
مزايا وعيوب البحث الثنائي
المزايا:
- الكفاءة: البحث الثنائي فعال للغاية، خاصة بالنسبة للقوائم الكبيرة. يتطلب عددًا قليلاً جدًا من الخطوات للعثور على العنصر المطلوب.
- الوقت اللوغاريتمي: تعقيد الوقت للبحث الثنائي هو O(log n)، حيث n هو حجم القائمة. هذا يعني أن الوقت المستغرق للبحث يزداد ببطء شديد مع زيادة حجم القائمة.
- سهولة التنفيذ: البحث الثنائي سهل التنفيذ نسبيًا.
العيوب:
- القائمة المرتبة: يتطلب البحث الثنائي أن تكون القائمة مرتبة. إذا كانت القائمة غير مرتبة، فيجب عليك أولاً ترتيبها، مما قد يستغرق وقتًا طويلاً.
- الإدخال والحذف: الإدخال والحذف في قائمة مرتبة مكلفان نسبيًا لأنهما يتطلبان تحريك عناصر أخرى في القائمة.
تحليل التعقيد الزمني
التعقيد الزمني لخوارزمية البحث الثنائي هو O(log n)، حيث n هو عدد العناصر في المصفوفة. وهذا يعني أن عدد الخطوات المطلوبة للعثور على عنصر ما يزداد لوغاريتميًا مع حجم المصفوفة. على سبيل المثال، إذا كانت المصفوفة تحتوي على 1024 عنصرًا، فستتطلب خوارزمية البحث الثنائي 10 خطوات على الأكثر للعثور على عنصر ما.
أفضل سيناريو: O(1) – عندما يكون العنصر المراد البحث عنه هو العنصر الأوسط في المصفوفة.
أسوأ سيناريو: O(log n) – عندما لا يكون العنصر موجودًا في المصفوفة، أو عندما يكون العنصر المراد البحث عنه في أبعد موقع ممكن.
المتوسط: O(log n)
تطبيقات البحث الثنائي
يستخدم البحث الثنائي على نطاق واسع في مجموعة متنوعة من التطبيقات، بما في ذلك:
- قواعد البيانات: تستخدم قواعد البيانات البحث الثنائي للعثور على سجلات محددة بسرعة.
- محركات البحث: تستخدم محركات البحث البحث الثنائي للعثور على صفحات الويب التي تتطابق مع استعلام بحث المستخدم.
- خوارزميات الضغط: تستخدم خوارزميات الضغط البحث الثنائي للعثور على أنماط متكررة في البيانات.
- المكتبات القياسية للغات البرمجة: العديد من اللغات مثل ++C و Java و Python توفر دوال بحث ثنائي جاهزة للاستخدام.
- تصحيح الأخطاء: يمكن استخدام البحث الثنائي لتحديد موقع الخطأ في البرنامج بكفاءة.
مثال بلغة بايثون
فيما يلي مثال لكيفية تنفيذ البحث الثنائي في بايثون:
“`python
def binary_search(list, target):
low = 0
high = len(list) – 1
while low <= high:
mid = (low + high) // 2
guess = list[mid]
if guess == target:
return mid
if guess > target:
high = mid – 1
else:
low = mid + 1
return None
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # Output: 1
print(binary_search(my_list, -1)) # Output: None
“`
تشرح هذه الدالة كيفية عمل البحث الثنائي: يتم تحديد نقطتي بداية ونهاية (low, high) للقائمة، ثم يتم حساب النقطة الوسطى (mid). إذا كان العنصر الموجود في النقطة الوسطى هو العنصر المطلوب، يتم إرجاع موقعه. إذا كان العنصر الموجود في النقطة الوسطى أكبر من العنصر المطلوب، يتم تحديث نقطة النهاية لتصبح النقطة الوسطى ناقص واحد. إذا كان العنصر الموجود في النقطة الوسطى أصغر من العنصر المطلوب، يتم تحديث نقطة البداية لتصبح النقطة الوسطى زائد واحد. تستمر هذه العملية حتى يتم العثور على العنصر أو حتى تصبح نقطة البداية أكبر من نقطة النهاية، مما يعني أن العنصر غير موجود في القائمة.
الاختلافات في البحث الثنائي
هناك عدة اختلافات للبحث الثنائي، بما في ذلك:
- البحث الثنائي المتكرر (Recursive Binary Search): يعتمد على استدعاء الدالة لنفسها لتقسيم المشكلة إلى مشاكل فرعية أصغر.
- البحث الثنائي الموحد (Uniform Binary Search): يهدف إلى تقليل عدد العمليات الحسابية داخل الحلقة.
- البحث الأسي (Exponential Search): يستخدم للبحث في قوائم غير محدودة الحجم.
- البحث الثلاثي (Ternary Search): يشبه البحث الثنائي لكنه يقسم المصفوفة إلى ثلاثة أجزاء بدلاً من جزأين.
اعتبارات عملية
عند تطبيق البحث الثنائي في سيناريوهات العالم الحقيقي، من الضروري مراعاة بعض الاعتبارات العملية:
- حجم البيانات: يكون البحث الثنائي أكثر فائدة للمجموعات الكبيرة من البيانات حيث تكون كفاءته أكثر وضوحًا. بالنسبة لمجموعات البيانات الصغيرة، قد يكون البحث الخطي أسرع بسبب النفقات العامة المرتبطة بتقسيم البيانات.
- الذاكرة المؤقتة (Caching): يمكن أن تؤثر الطريقة التي يتم بها تنظيم البيانات في الذاكرة على أداء البحث الثنائي. يمكن أن يؤدي الاستفادة من الذاكرة المؤقتة إلى تحسين السرعة.
- توزيع البيانات: يمكن أن يؤثر توزيع البيانات داخل المصفوفة على أداء البحث. في بعض الحالات، قد تكون هياكل البيانات الأخرى أو الخوارزميات أكثر ملاءمة.
خاتمة
البحث الثنائي هو خوارزمية قوية وفعالة للبحث عن العناصر في قائمة مرتبة. يتميز ببساطته وسرعته، مما يجعله أداة أساسية في علم الحاسوب. على الرغم من أنه يتطلب قائمة مرتبة، إلا أن فوائده في الأداء تفوق هذا القيد في العديد من التطبيقات. فهم آلية عمله ومزاياه وعيوبه وتطبيقاته يجعلك مبرمجًا أفضل وأكثر كفاءة.