خوارزمية البحث الثنائي (Binary Search) في C++- الشرح والمثال والكود

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

كيف تعمل

1. ابدأ بالقائمة التي تم فرزها بالكامل.
2. ابحث عن العنصر الأوسط لنطاق البحث الحالي.
3. قارن العنصر الأوسط بالقيمة المستهدفة.
4. إذا كان العنصر الأوسط يساوي القيمة المستهدفة، يكون البحث ناجحاً.
5. إذا كان العنصر الأوسط أكبر من الهدف، ابحث في النصف الأيسر من النطاق.
6. إذا كان العنصر الأوسط أصغر من الهدف، فابحث في النصف الأيمن من النطاق.
7. كرر الخطوات من 2 إلى 6 حتى يتم العثور على العنصر الهدف أو يصبح نطاق البحث فارغًا.

مثال

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

القائمة المرتبة: {12، 23، 34، 45، 56، 67، 89، 90}

1. ابدأ بالقائمة بأكملها.
2. العنصر الأوسط: 56(الموضع 4). قارن مع 34.
3. 56 أكبر من 34. ابحث في النصف الأيسر.
4. العنصر الأوسط الجديد: 23(الموضع 1). قارن مع 34.
5. 23 أصغر من 34. ابحث في النصف الأيمن.
6. العنصر الأوسط الجديد: 45(الموضع 3). قارن مع 34.
7. 45 أكبر من 34. ابحث في النصف الأيسر.
8. العنصر الأوسط الجديد: 34(الموضع 2). تم العثور على الهدف.

رمز المثال في C++

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

في المثال الموضح، binarySearch يتم استخدام الدالة للعثور على الرقم 34 في قائمة مرتبة من الأعداد الصحيحة. ستكون النتيجة موضع 34 في القائمة(تبدأ المواضع من 0) أو -1 إذا لم يتم العثور على الرقم.