خوارزمية البحث الثنائي (Binary Search) في PHP: الشرح والخطوات والمثال

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

خطوات:

1. بدء نطاق البحث: ابدأ بتحديد نطاق البحث من الموضع الأول left  إلى آخر موضع right  للمصفوفة.
2. ابحث عن النقطة الوسطى: احسب النقطة الوسطى عن طريق حساب متوسط left ​​المواضع الصحيحة ؛ هذه هي النقطة الوسطى من نطاق البحث.
3. قارن القيم: قارن القيمة في النقطة الوسطى مع القيمة المستهدفة.
4. معالجة نتيجة المقارنة: إذا كانت القيمة الموجودة في النقطة الوسطى تتطابق مع القيمة المستهدفة ، فقم بإرجاع هذا الموضع. إذا كانت القيمة الموجودة في النقطة الوسطى أقل من القيمة المستهدفة ، فقم بتحديث الموضع الأيسر إلى المنتصف + 1 للبحث في النصف الأيمن. إذا كانت القيمة الموجودة في النقطة الوسطى أكبر من القيمة المستهدفة ، فقم بتحديث الموضع الأيمن إلى المنتصف- 1 للبحث في النصف الأيسر.
5. كرر: كرر الخطوات من 2 إلى 4 حتى يتم العثور على القيمة أو عدم وجود المزيد من العناصر للتحقق منها left > right.

المميزات والعيوب

مزايا:

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

سلبيات:

• قابل للتطبيق فقط على المصفوفات التي تم فرزها: تعمل الخوارزمية فقط على المصفوفات التي تم فرزها.
• عدد الخطوات المتغير: يعتمد عدد الخطوات المطلوبة للعثور على القيمة على موضعها في المصفوفة ، ويمكن أن يستغرق العديد من الخطوات للقيم القريبة من النهايات.

مثال: بحث ثنائي لإيجاد القيمة 12 في مصفوفة مرتبة في PHP

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}  

شرح المثال

1. نبدأ بمدى البحث الأولي من الموضع الأول left = 0 إلى الموضع الأخير right = 6  للمصفوفة.
2. نحسب النقطة الوسطى(الوسط) عن طريق حساب متوسط ​​المواضع اليمنى واليسرى ؛ mid = 3. القيمة عند منتصف هي 12.
3. نقارن القيمة عند mid(12) بالقيمة المستهدفة(12) ونجد تطابقًا ، لذلك نعيد الموضع 3.
4. تنتهي الخوارزمية ، ونخرج النتيجة "تم العثور على القيمة 12 في الموضع 3."