البحث الثنائي (Binary Search)

البحث الثنائي هو طريقة سريعة لإيجاد عنصر في قائمة أو نطاق مرتبة. لكن قبل ذلك، لنبدأ بشيء أبسط — البحث الخطي (linear search).

البحث الخطي

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {4, 8, 15, 16, 23, 42};
    int target = 15;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            cout << "Found at index " << i;
            return 0;
        }
    }
    cout << "Not found";
}

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

إذا كان هناك مليون رقم، فهذا يعني مليون عملية تحقق.

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

هذا هو البحث الثنائي.

فكرة البحث الثنائي

البحث الثنائي يشبه لعبة “خمن الرقم”. كل مرة تختار القيمة الوسطى وتسأل:

• هل هذه القيمة صغيرة جدًا؟
• كبيرة جدًا؟
• أم صحيحة بالضبط؟

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

البحث الثنائي الكلاسيكي

Find the 7

Find the 7

لدينا مصفوفة مرتبة:

[1, 3, 5, 6, 7, 9, 11]

ابحث عن الرقم 7 في المصفوفة واطبع موقعه إذا وجد.

Solution

نبدأ بالنطاق الكامل، ثم نضيق البحث تدريجيًا.

أولًا، نجد العنصر في المنتصف، وهو الرقم 6. نسأل هل الرقم 7 أصغر أم أكبر من 6؟ هو أكبر، وبما أن المصفوفة مرتبة، هذا يعني أن الرقم 7 سيكون بعد 6. يمكننا تجاهل النصف الأول من المصفوفة.

المصفوفة المتبقية هي [7, 9, 11]. العنصر في المنتصف هو 9. الرقم 7 أصغر من 9، أي أنه قبل 9 في المصفوفة المرتبة. يمكننا تجاهل 9 وكل ما بعده.

أخيرًا، المصفوفة هي [7]. العنصر الأوسط هو 7، وهو ما نبحث عنه بالضبط. قُمنا بثلاث مقارنات:

• قارننا 6 مع 7
• قارننا 9 مع 7
• قارننا 7 مع 7

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 6, 7, 9, 11};
    int target = 7;
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            cout << "Found at index " << mid;
            return 0;
        } else if (arr[mid] < target) 
            left = mid + 1;
        else 
            right = mid - 1;
    }

    cout << "Not found";
}

المخرجات:

Found at index 4

كل خطوة تقطع النطاق إلى النصف. إذا كان هناك n عنصرًا، البحث الثنائي يحتاج حوالي \(\log_2(n)\) خطوة فقط. أي حوالي 20 تحقق، حتى لو كان هناك مليون رقم.

إيجاد أول عنصر أكبر من أو يساوي X

البحث الثنائي يمكنه فعل أكثر من إيجاد رقم. يمكن استخدامه لإيجاد مواضع أو حدود.

Position Hunt

Position Hunt

لديك مصفوفة [2, 4, 6, 8, 10]. اعثر على أول عنصر أكبر من أو يساوي 7 باستخدام البحث الثنائي.

Solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {2, 4, 6, 8, 10};
    int x = 7;

    int left = 0, right = arr.size() - 1;
    int ans = -1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] >= x) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (ans == -1) cout << "No element found";
    else cout << "First element >= " << x << " is at index " << ans;
}

المخرجات:

First element >= 7 is at index 3

أي أن arr[3] = 8 هو أول عنصر أكبر من أو يساوي 7.

الخوارزمية

1. ابدأ بمؤشرين left و right.
2. احسب منتصف النطاق mid.
3. إذا كانت القيمة الوسطى هي الإجابة، توقف.
4. إذا كانت صغيرة جدًا، حرك left إلى mid + 1.
5. إذا كانت كبيرة جدًا، حرك right إلى mid - 1.
6. كرر حتى يصبح left > right.