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

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

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

مقدمة

يعد البحث أحد أكثر العمليات شيوعًا في البرمجة. غالبًا ما يحتاج المطورون إلى العثور على رقم معين أو مستخدم أو منتج أو سجل أو معرف (ID) أو تاريخ أو قيمة داخل مجموعة من البيانات.

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

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

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

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

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

الفكرة الرئيسية بسيطة:

• ابدأ بالمصفوفة المرتبة بالكامل.

• ابحث عن العنصر الأوسط.

• قارن العنصر الأوسط بالقيمة المستهدفة.

• إذا تم العثور على القيمة المستهدفة، أرجع مؤشرها.

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

• إذا كانت القيمة المستهدفة أكبر، ابحث في النصف الأيمن.

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

يسمى البحث الثنائي “ثنائيًا” لأن كل خطوة تقسم مساحة البحث إلى جزأين.

المتطلب الأهم

يعمل البحث الثنائي بشكل صحيح فقط عندما تكون المصفوفة مرتبة.

على سبيل المثال، هذه المصفوفة مرتبة:

[2, 4, 6, 8, 10, 12, 14]

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

لكن هذه المصفوفة غير مرتبة:

[8, 2, 14, 4, 10, 6, 12]

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

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

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

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

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

على سبيل المثال:

• في مصفوفة تتكون من 16 عنصرًا، يحتاج البحث الثنائي إلى حوالي 4 فحوصات كحد أقصى.

• في مصفوفة تتكون من 1,024 عنصرًا، يحتاج إلى حوالي 10 فحوصات كحد أقصى.

• في مصفوفة تتكون من 1,000,000 عنصر، يحتاج إلى حوالي 20 فحصًا.

هذه الكفاءة هي السبب في أن البحث الثنائي خوارزمية أساسية في علوم الكمبيوتر.

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

يتتبع البحث الثنائي حدين: الحد الأيسر والحد الأيمن. تحدد هذه الحدود نطاق البحث الحالي.

في كل خطوة، تحسب الخوارزمية المؤشر الأوسط:

middle = left + (right - left) / 2

ثم تقارن القيمة الوسطى بالقيمة المستهدفة.

إذا كانت القيمة الوسطى صغيرة جدًا، يجب أن تكون القيمة المستهدفة على الجانب الأيمن. إذا كانت القيمة الوسطى كبيرة جدًا، يجب أن تكون القيمة المستهدفة على الجانب الأيسر. إذا تطابقت القيمة الوسطى مع القيمة المستهدفة، تُرجع الخوارزمية المؤشر الأوسط.

تستمر هذه العملية حتى يصبح نطاق البحث فارغًا.

مثال تشغيل يدوي

دعنا نبحث يدويًا عن القيمة المستهدفة 14 في المصفوفة المرتبة التالية:

[2, 4, 6, 8, 10, 12, 14, 16, 18]

القيمة المستهدفة هي:

Target = 14

مؤشرات المصفوفة هي:

Index:  0  1  2  3   4   5   6   7   8
Value:  2  4  6  8  10  12  14  16  18

الخطوة 1: تعيين الحدود الأولية

في البداية، يكون الحد الأيسر هو المؤشر الأول والحد الأيمن هو المؤشر الأخير.

left = 0
right = 8

الآن نحسب المؤشر الأوسط:

middle = 0 + (8 - 0) / 2 = 4

القيمة الوسطى هي:

array[4] = 10

قارن القيمة الوسطى بالقيمة المستهدفة:

10 == 14 ? No
10 < 14 ? Yes

بما أن 10 أصغر من 14، يجب أن تكون القيمة المستهدفة في النصف الأيمن.

لذلك ننقل الحد الأيسر:

left = middle + 1 = 5

الخطوة 2: البحث في النصف الأيمن

نطاق البحث الحالي الآن هو:

[12, 14, 16, 18]

الحدود هي:

left = 5
right = 8

احسب المؤشر الأوسط:

middle = 5 + (8 - 5) / 2 = 6

القيمة الوسطى هي:

array[6] = 14

قارن القيمة الوسطى بالقيمة المستهدفة:

14 == 14 ? Yes

تم العثور على القيمة المستهدفة عند المؤشر 6.

نتيجة البحث

Target 14 found at index 6

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

تشغيل يدوي عندما لا يتم العثور على القيمة

الآن دعنا نبحث عن القيمة المستهدفة 15 في نفس المصفوفة المرتبة:

[2, 4, 6, 8, 10, 12, 14, 16, 18]

القيمة المستهدفة هي:

Target = 15

الخطوة 1

الحدود الأولية:

left = 0
right = 8

المؤشر الأوسط:

middle = 4

القيمة الوسطى:

array[4] = 10

بما أن 10 أصغر من 15، ابحث في النصف الأيمن:

left = 5
right = 8

الخطوة 2

نطاق البحث الحالي:

[12, 14, 16, 18]

المؤشر الأوسط:

middle = 6

القيمة الوسطى:

array[6] = 14

بما أن 14 أصغر من 15، ابحث في النصف الأيمن:

left = 7
right = 8

الخطوة 3

نطاق البحث الحالي:

[16, 18]

المؤشر الأوسط:

middle = 7

القيمة الوسطى:

array[7] = 16

بما أن 16 أكبر من 15، ابحث في النصف الأيسر:

left = 7
right = 6

الآن أصبح الحد الأيسر أكبر من الحد الأيمن. هذا يعني أن نطاق البحث فارغ.

نتيجة البحث

Target 15 was not found

تتوقف الخوارزمية لأنه لا يوجد جزء متبقي من المصفوفة للبحث فيه.

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

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

1. استقبل مصفوفة مرتبة وقيمة مستهدفة.

2. عيّن left إلى 0.

3. عيّن right إلى المؤشر الأخير للمصفوفة.

4. طالما أن left أقل من أو يساوي right، احسب المؤشر الأوسط.

5. إذا كانت القيمة الوسطى تساوي القيمة المستهدفة، أرجع المؤشر الأوسط.

6. إذا كانت القيمة الوسطى أقل من القيمة المستهدفة، حرّك left إلى middle + 1.

7. إذا كانت القيمة الوسطى أكبر من القيمة المستهدفة، حرّك right إلى middle - 1.

8. إذا انتهت الحلقة، أرجع -1 لأن القيمة المستهدفة لم تُعثر عليها.

لا يتطلب هذا الإصدار العودية (recursion) وغالبًا ما يكون الأسهل للاستخدام في الكود العملي.

الكود الزائف (Pseudocode)

binarySearch(array, target):
    left = 0
    right = length(array) - 1

    while left <= right:
        middle = left + (right - left) / 2

        if array[middle] == target:
            return middle

        if array[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

تُرجع الدالة مؤشر القيمة المستهدفة إذا كانت موجودة. إذا لم تكن القيمة المستهدفة موجودة، تُرجع -1.

مثال على البحث الثنائي في PHP

إليك تطبيق PHP تكراري نظيف للبحث الثنائي:

<?php

function binarySearch(array $numbers, int $target): int
{
    $left = 0;
    $right = count($numbers) - 1;

    while ($left <= $right) {
        $middle = $left + intdiv($right - $left, 2);

        if ($numbers[$middle] === $target) {
            return $middle;
        }

        if ($numbers[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return -1;
}

$numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

echo binarySearch($numbers, 14);

سيكون الإخراج:

6

القيمة المستهدفة 14 موجودة عند المؤشر 6، لذا تُرجع الدالة 6.

البحث الثنائي في PHP عندما لا يتم العثور على القيمة

إذا بحثنا عن قيمة غير موجودة:

<?php

$numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

echo binarySearch($numbers, 15);

سيكون الإخراج:

-1

القيمة 15 غير موجودة في المصفوفة، لذا تُرجع الدالة -1.

مثال على البحث الثنائي في JavaScript

إليك نفس الخوارزمية مطبقة في JavaScript:

function binarySearch(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left <= right) {
        const middle = left + Math.floor((right - left) / 2);

        if (numbers[middle] === target) {
            return middle;
        }

        if (numbers[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

const numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

console.log(binarySearch(numbers, 14));

سيكون الإخراج:

6

تتبع نسخة JavaScript نفس منطق نسخة PHP. فهي تتحقق بشكل متكرر من القيمة الوسطى وتزيل نصف نطاق البحث.

البحث الثنائي العودي (Recursive Binary Search)

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

الفكرة العودية هي:

• إذا كان النطاق فارغًا، أرجع -1.

• افحص العنصر الأوسط.

• إذا تم العثور على القيمة المستهدفة، أرجع المؤشر الأوسط.

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

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

النسخة العودية أنيقة، لكن النسخة التكرارية عادة ما تكون أكثر كفاءة في استخدام الذاكرة لأنها لا تنشئ إطارات مكدس استدعاء عودية.

البحث الثنائي العودي في PHP

<?php

function recursiveBinarySearch(array $numbers, int $target, int $left, int $right): int
{
    if ($left > $right) {
        return -1;
    }

    $middle = $left + intdiv($right - $left, 2);

    if ($numbers[$middle] === $target) {
        return $middle;
    }

    if ($numbers[$middle] > $target) {
        return recursiveBinarySearch($numbers, $target, $left, $middle - 1);
    }

    return recursiveBinarySearch($numbers, $target, $middle + 1, $right);
}

$numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

echo recursiveBinarySearch($numbers, 14, 0, count($numbers) - 1);

سيكون الإخراج:

6

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

البحث الثنائي العودي في JavaScript

function recursiveBinarySearch(numbers, target, left = 0, right = numbers.length - 1) {
    if (left > right) {
        return -1;
    }

    const middle = left + Math.floor((right - left) / 2);

    if (numbers[middle] === target) {
        return middle;
    }

    if (numbers[middle] > target) {
        return recursiveBinarySearch(numbers, target, left, middle - 1);
    }

    return recursiveBinarySearch(numbers, target, middle + 1, right);
}

const numbers = [2, 4, 6, 8, 10, 12, 14, 16, 18];

console.log(recursiveBinarySearch(numbers, 14));

سيكون الإخراج:

6

هذه النسخة مفيدة لتعلم العودية، لكن النسخة التكرارية غالبًا ما تكون مفضلة في كود الإنتاج.

لماذا نحسب المنتصف بهذه الطريقة؟

قد ترى المؤشر الأوسط محسوبًا هكذا:

middle = (left + right) / 2

يعمل هذا مع الأرقام الصغيرة، ولكن في بعض لغات البرمجة، يمكن أن يؤدي جمع left و right مباشرة إلى تجاوز سعة العدد الصحيح (integer overflow) عندما تكون المؤشرات كبيرة جدًا.

صيغة أكثر أمانًا هي:

middle = left + (right - left) / 2

هذا يتجنب جمع مؤشرين قد يكونان كبيرين معًا. في أمثلة PHP و JavaScript، استخدمنا هذا النمط الأكثر أمانًا.

التعقيد الزمني للبحث الثنائي

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

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

• أفضل حالة: O(1)

• الحالة المتوسطة: O(log n)

• أسوأ حالة: O(log n)

حيث n هو عدد العناصر في المصفوفة المرتبة.

أفضل حالة للتعقيد الزمني: O(1)

تحدث أفضل حالة عندما يتم العثور على القيمة المستهدفة في الموضع الأوسط عند الفحص الأول.

Array:  [2, 4, 6, 8, 10]
Target: 6

القيمة الوسطى هي 6، لذا تجد الخوارزمية القيمة المستهدفة على الفور.

لذلك، أفضل حالة للتعقيد الزمني هي:

O(1)

وهذا يعني وقتًا ثابتًا لأن مقارنة واحدة فقط مطلوبة.

الحالة المتوسطة للتعقيد الزمني: O(log n)

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

على سبيل المثال، إذا كانت المصفوفة تحتوي على 16 عنصرًا، يصبح نطاق البحث:

16 → 8 → 4 → 2 → 1

ينمو عدد الخطوات لوغاريتميًا، وليس خطيًا.

لذلك، الحالة المتوسطة للتعقيد الزمني هي:

O(log n)

أسوأ حالة للتعقيد الزمني: O(log n)

تحدث أسوأ حالة عندما تكون القيمة المستهدفة في آخر موضع ممكن فحصه أو عندما لا تكون القيمة المستهدفة موجودة في المصفوفة.

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

على سبيل المثال، مع 1,024 عنصرًا:

1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

يستغرق هذا حوالي 10 خطوات لأن:

log2(1024) = 10

لذلك، أسوأ حالة للتعقيد الزمني هي:

O(log n)

لماذا البحث الثنائي هو O(log n)؟

البحث الثنائي هو O(log n) لأن كل مقارنة تزيل نصف العناصر المتبقية من الاعتبار.

إذا تضاعف حجم الإدخال، يحتاج البحث الثنائي عادةً إلى خطوة إضافية واحدة فقط.

Elements: 8       Maximum steps: 3
Elements: 16      Maximum steps: 4
Elements: 32      Maximum steps: 5
Elements: 1024    Maximum steps: 10
Elements: 1,048,576 Maximum steps: 20

هذا النمو البطيء هو ما يجعل البحث الثنائي فعالاً للغاية لمجموعات البيانات الكبيرة والمرتبة.

التعقيد المكاني للبحث الثنائي

يصف التعقيد المكاني مقدار الذاكرة الإضافية التي تستخدمها الخوارزمية.

تستخدم النسخة التكرارية للبحث الثنائي عددًا قليلاً فقط من المتغيرات:

• left

• right

• middle

• target

لا ينشئ مصفوفة أو بنية بيانات جديدة.

لذلك، التعقيد المكاني للبحث الثنائي التكراري هو:

O(1)

تستخدم النسخة العودية مكدس الاستدعاءات (call stack). ولأن عمق العودية هو O(log n)، فإن التعقيد المكاني للبحث الثنائي العودي هو:

O(log n)

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

البحث الثنائي والبحث الخطي كلاهما خوارزميات بحث، ولكنهما يستخدمان في مواقف مختلفة.

يفحص البحث الخطي العناصر واحدًا تلو الآخر. يقسم البحث الثنائي نطاق البحث إلى النصف بشكل متكرر.

الاختلافات الرئيسية تشمل:

• يعمل البحث الخطي على البيانات غير المرتبة.

• يتطلب البحث الثنائي بيانات مرتبة.

• يحتوي البحث الخطي على تعقيد زمني في أسوأ الحالات O(n).

• يحتوي البحث الثنائي على تعقيد زمني في أسوأ الحالات O(log n).

• البحث الخطي أبسط.

• البحث الثنائي أسرع بكثير للمصفوفات الكبيرة المرتبة.

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

البحث الثنائي مع القيم المكررة

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

على سبيل المثال:

Array:  [2, 4, 4, 4, 6, 8]
Target: 4

قد يُرجع البحث الثنائي المؤشر 1 أو 2 أو 3 اعتمادًا على كيفية حساب المؤشر الأوسط أثناء البحث.

إذا احتاج المطورون إلى الظهور الأول أو الأخير، يجب تعديل الخوارزمية.

إيجاد أول ظهور

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

<?php

function firstOccurrence(array $numbers, int $target): int
{
    $left = 0;
    $right = count($numbers) - 1;
    $result = -1;

    while ($left <= $right) {
        $middle = $left + intdiv($right - $left, 2);

        if ($numbers[$middle] === $target) {
            $result = $middle;
            $right = $middle - 1;
        } elseif ($numbers[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return $result;
}

$numbers = [2, 4, 4, 4, 6, 8];

echo firstOccurrence($numbers, 4);

سيكون الإخراج:

1

تخزن هذه النسخة المؤشر الذي تم العثور عليه وتستمر في البحث يسارًا لمعرفة ما إذا كان هناك ظهور سابق.

إيجاد آخر ظهور

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

<?php

function lastOccurrence(array $numbers, int $target): int
{
    $left = 0;
    $right = count($numbers) - 1;
    $result = -1;

    while ($left <= $right) {
        $middle = $left + intdiv($right - $left, 2);

        if ($numbers[$middle] === $target) {
            $result = $middle;
            $left = $middle + 1;
        } elseif ($numbers[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return $result;
}

$numbers = [2, 4, 4, 4, 6, 8];

echo lastOccurrence($numbers, 4);

سيكون الإخراج:

3

تخزن هذه النسخة المؤشر الذي تم العثور عليه وتستمر في البحث يمينًا للعثور على آخر موضع مطابق.

البحث الثنائي على المصفوفات التنازلية

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

على سبيل المثال:

[18, 16, 14, 12, 10, 8, 6, 4, 2]

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

هذا هو السبب في أنه يجب على المطورين معرفة اتجاه الفرز قبل تطبيق البحث الثنائي.

البحث الثنائي على الإجابة

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

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

تشمل الأمثلة:

• إيجاد الحد الأدنى للسعة المطلوبة لشحن الطرود خلال عدد معين من الأيام.

• إيجاد أصغر سرعة مطلوبة لإنهاء مهمة قبل الموعد النهائي.

• إيجاد أول نسخة معيبة في تسلسل من الإصدارات.

• إيجاد حد أدنى (lower bound) أو حد أعلى (upper bound) في نطاق مرتب.

غالبًا ما تسمى هذه التقنية “البحث الثنائي على الإجابة” وهي شائعة في حل المشكلات والبرمجة التنافسية.

الحد الأدنى والحد الأعلى

يمكن تعديل البحث الثنائي لإيجاد الحدود بدلاً من القيم الدقيقة.

الحد الأدنى (Lower bound) يعني عادةً الموضع الأول الذي يمكن إدراج قيمة فيه دون كسر الترتيب المصنف. يجد أول عنصر أكبر من أو يساوي القيمة المستهدفة.

الحد الأعلى (Upper bound) يعني عادةً الموضع الأول الأكبر من القيمة المستهدفة.

هذه المتغيرات مفيدة عند التعامل مع التكرارات، النطاقات، القوائم المرتبة، ومواضع الإدراج.

متى يجب على المطورين استخدام البحث الثنائي؟

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

البحث الثنائي مفيد عندما:

• تكون المصفوفة مرتبة.

• مجموعة البيانات كبيرة.

• تحدث عمليات البحث بشكل متكرر.

• يتوفر الوصول العشوائي عن طريق المؤشر.

• يمكن تقسيم مشكلة البحث إلى نصفين.

• هناك حاجة لحل لوغاريتمي.

• المشكلة لها شرط رتيب (monotonic condition).

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

متى لا يجب استخدام البحث الثنائي؟

لا ينبغي استخدام البحث الثنائي عندما تكون البيانات غير مرتبة ولا يستحق فرزها أولاً التكلفة.

يجب على المطورين تجنب البحث الثنائي عندما:

• المصفوفة غير مرتبة.

• مجموعة البيانات صغيرة جدًا والبحث الخطي أبسط.

• بنية البيانات لا تدعم الوصول العشوائي السريع.

• قاعدة المقارنة غير متسقة.

• البيانات تتغير باستمرار والحفاظ على ترتيبها مكلف.

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

مثال عملي: البحث عن أسعار المنتجات

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

<?php

$prices = [19, 29, 49, 79, 99, 149, 199];

echo binarySearch($prices, 79);

سيكون الإخراج:

3

السعر 79 موجود عند المؤشر 3.

مثال عملي: البحث عن معرفات المستخدمين (User IDs)

إذا تم تخزين معرفات المستخدمين (User IDs) بترتيب مصنف، يمكن للبحث الثنائي التحقق بسرعة مما إذا كان معرف معين موجودًا.

User IDs:
[101, 105, 109, 120, 135, 150, 180]

Target:
135

يمكن للبحث الثنائي العثور على 135 دون فحص كل معرف واحدًا تلو الآخر.

في أنظمة الواجهة الخلفية (backend) الحقيقية، تتعامل فهارس قواعد البيانات (database indexes) عادة مع هذا النوع من البحث بكفاءة أكبر. ومع ذلك، فإن الفكرة الكامنة وراء البحث المفهرس (indexed search) مرتبطة بتجنب عمليات المسح الخطي الكاملة كلما أمكن ذلك.

أخطاء شائعة عند تطبيق البحث الثنائي

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

الأخطاء الشائعة تشمل:

• استخدام البحث الثنائي على مصفوفة غير مرتبة.

• استخدام شرط الحلقة الخاطئ.

• نسيان تحديث left أو right.

• استخدام middle مرة أخرى بدلاً من middle + 1 أو middle - 1.

• إنشاء حلقة لا نهائية (infinite loop).

• حساب المؤشر الأوسط بشكل غير صحيح.

• عدم معالجة المصفوفات الفارغة.

• توقع أن يعيد البحث الثنائي العادي دائمًا أول قيمة مكررة.

القاعدة الأهم هي تقليص نطاق البحث بشكل صحيح بعد كل مقارنة.

قائمة تحقق عملية لفهم البحث الثنائي

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

• لماذا يجب أن تكون المصفوفة مرتبة؟

• ماذا يمثل left و right؟

• كيف يتم حساب المؤشر الأوسط؟

• متى يجب أن تبحث الخوارزمية في النصف الأيسر؟

• متى يجب أن تبحث الخوارزمية في النصف الأيمن؟

• ما هو شرط التوقف؟

• لماذا التعقيد الزمني هو O(log n)؟

• ما الفرق بين البحث الثنائي التكراري والعودي؟

• كيف يجب التعامل مع القيم المكررة؟

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

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

يتمتع البحث الثنائي بالعديد من المزايا المهمة.

• إنه فعال للغاية للمصفوفات الكبيرة المرتبة.

• لديه تعقيد زمني O(log n) في الحالة المتوسطة وأسوأ الحالات.

• يستخدم ذاكرة إضافية O(1) في النسخة التكرارية.

• سهل التكييف لأول ظهور، آخر ظهور، الحد الأدنى، والحد الأعلى.

• يعلم التفكير اللوغاريتمي ومنطق التقسيم والحل.

• مفيد في العديد من المشكلات الخوارزمية التي تتجاوز البحث البسيط.

هذه المزايا تجعل البحث الثنائي أحد أهم الخوارزميات التي يجب على المطورين إتقانها.

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

البحث الثنائي له أيضًا قيود.

• يتطلب بيانات مرتبة.

• إنه أكثر تعقيدًا من البحث الخطي.

• ليس مثاليًا لهياكل البيانات التي لا تدعم الوصول السريع بالمؤشر.

• قد يتطلب الفرز أولاً، والذي له تكلفته الخاصة.

• يمكن تطبيقه بشكل غير صحيح إذا كانت تحديثات الحدود خاطئة.

بسبب هذه القيود، يكون البحث الثنائي قويًا فقط عندما يتم تلبية متطلباته.

البحث الثنائي في مشاريع البرمجيات الحقيقية

في مشاريع البرمجيات الحقيقية، لا يقوم المطورون عادةً بتطبيق البحث الثنائي يدويًا لكل مشكلة بحث. غالبًا ما توفر لغات البرمجة وقواعد البيانات ومحركات البحث والمكتبات آليات بحث وفهرسة محسّنة.

ومع ذلك، لا يزال فهم البحث الثنائي ذا قيمة لأن نفس الفكرة تظهر في العديد من الأماكن. تعتمد فهارس قواعد البيانات (Database indexes)، والمجموعات المرتبة، واستعلامات النطاق (range queries)، وحدود الترقيم (pagination boundaries)، وفحوصات الإصدارات (version checks)، ومشكلات التحسين، وتحديات الخوارزميات غالبًا على تفكير البحث الثنائي.

بالنسبة لمطوري الواجهة الخلفية (backend developers)، يساعد البحث الثنائي أيضًا في بناء حدس أقوى حول سبب كون الاستعلامات المفهرسة أسرع من مسح كل سجل.

الخاتمة

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

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

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

يمكن تطبيق البحث الثنائي بشكل تكراري أو عودي. تستخدم النسخة التكرارية مساحة إضافية O(1)، بينما تستخدم النسخة العودية مساحة مكدس O(log n). يمكن أيضًا توسيع الخوارزمية للتعامل مع التكرارات، والحدود الدنيا، والحدود العليا، ومشكلات البحث عن الإجابة.

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