المستوى: مبتدئ — المقال ده مكتوب لحد لسه بادئ في الخوارزميات. كل مفهوم هتلاقيه متشرح بمثال بسيط الأول، وبعدها بشكل علمي دقيق. وقت القراءة المتوقع حوالي 6 دقائق.

Binary Search للمبتدئ: ليه البحث في مليون عنصر بياخد 20 خطوة بس

لو بتدوّر على رقم في قائمة فيها مليون عنصر، الطريقة الساذجة بتمر على العناصر واحد واحد لحد ما تلاقيه. البحث الثنائي (Binary Search) بيوصل لنفس العنصر في 20 مقارنة بحد أقصى. هنا هتفهم ليه بالظبط، وإمتى تستخدمه، وإمتى متستخدموش.

المشكلة باختصار

تخيّل عندك مصفوفة مرتبة فيها مليون رقم، وعايز تعرف الرقم 734219 موجود ولا لأ. لو مشيت عليها عنصر عنصر (linear search)، في أسوأ حالة هتعمل مليون مقارنة. ده شغّال، بس بيكبر مع البيانات. لو البيانات بقت 100 مليون، المقارنات تبقى 100 مليون. المشكلة مش في سرعة السيرفر، المشكلة إنك بتفحص كل حاجة من غير داعي.

الفكرة بمثال: القاموس

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

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

الشرح العلمي: ليه 20 خطوة؟

كل خطوة في البحث الثنائي بتقسم مساحة البحث على 2. ابتديت بمليون، بعد خطوة بقت 500 ألف، بعد التانية 250 ألف، وهكذا. السؤال: كام مرة تقدر تقسم مليون على 2 لحد ما توصل لـ 1؟ الإجابة هي لوغاريتم مليون للأساس 2.

الحساب: log₂(1,000,000) ≈ 19.93، يعني 20 خطوة. وعشان تحس بالفرق: 2¹⁰ = 1024 (تقريبًا ألف، ~10 خطوات)، و2²⁰ = 1,048,576 (أكتر من مليون، ~20 خطوة). ده معناه إن تعقيد البحث الثنائي هو O(log n)، مقابل O(n) للبحث الخطي. الـ trade-off هنا واضح: بتكسب سرعة هائلة، مقابل شرط واحد إن البيانات تكون مرتبة.

الكود: implementation شغّال

دي النسخة بلغة Python على مصفوفة مرتبة:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid          # لقيناه، رجّع الموقع
        elif arr[mid] < target:
            low = mid + 1        # روح للنص اليمين
        else:
            high = mid - 1       # روح للنص الشمال
    return -1                    # مش موجود

data = list(range(1_000_000))        # مصفوفة مرتبة من 0 لـ 999999
print(binary_search(data, 734219))   # 734219
print(binary_search(data, -5))       # -1

ونفس المنطق بـ JavaScript:

function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

ركز في نقطة بتوقّع ناس كتير: بنستخدم low <= high مش low < high، عشان منفوّتش آخر عنصر في المصفوفة. ده من أشهر الأخطاء في كتابة البحث الثنائي بإيدك.

الفرق بالأرقام

على مصفوفة مرتبة فيها مليون عنصر، أسوأ حالة:

• البحث الخطي (linear): حتى 1,000,000 مقارنة.
• البحث الثنائي (binary): 20 مقارنة بحد أقصى.

والفرق بيتوحّش مع الكبر. عند مليار عنصر، البحث الثنائي بياخد 30 مقارنة بس، لإن log₂(1,000,000,000) ≈ 30. في بايثون مش محتاج تكتبه بإيدك أصلًا؛ موديول bisect الرسمي جاهز:

from bisect import bisect_left

def exists(arr, x):
    i = bisect_left(arr, x)
    return i < len(arr) and arr[i] == x

الـ trade-offs اللي لازم تعرفها

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

كمان: الإدراج في مصفوفة مرتبة بيكلّف O(n)، عشان لازم تزحزح العناصر اللي بعد مكان الإدراج. والبحث الثنائي محتاج وصول عشوائي (random access)، يعني بيشتغل كويس على المصفوفات (arrays) مش على القوائم المترابطة (linked lists) اللي مفيهاش قفز مباشر لعنصر النص.

متى لا تستخدم هذه الطريقة

• لو المصفوفة صغيرة (أقل من ~50 عنصر) — البحث الخطي أبسط والفرق مش محسوس.
• لو البيانات بتتغير كتير (إضافة وحذف مستمر) — تكلفة الحفاظ على الترتيب بتاكل المكسب.
• لو مش محتاج ترتيب أصلًا والمطلوب وجود/عدم وجود فقط — جدول الهاش (hash table / dict) بيديك O(1) في المتوسط.
• لو هيكل بياناتك linked list — مفيش random access، فالبحث الثنائي بيفقد ميزته الأساسية.

الخطوة التالية

خُد أي مصفوفة مرتبة في مشروعك دلوقتي، وبدّل البحث الخطي (loop أو in) بـ bisect_left في بايثون أو دالة binarySearch اللي فوق. قِس الزمن قبل وبعد على مصفوفة فيها 100 ألف عنصر فأكتر. لو الفرق مش محسوس، يبقى مصفوفتك صغيرة والبحث الخطي كفاية — وده قرار صح برضه.

المصادر

• Cormen, Leiserson, Rivest, Stein — "Introduction to Algorithms" (CLRS): قسم البحث وتعقيد O(log n).
• Donald Knuth — "The Art of Computer Programming", Vol. 3: Sorting and Searching: قسم البحث الثنائي.
• توثيق Python الرسمي لموديول bisect: docs.python.org/3/library/bisect.html
• MDN Web Docs — Array في JavaScript: developer.mozilla.org
• Wikipedia — Binary search algorithm: قيمة log₂(1,000,000) ≈ 20 والتعقيد O(log n).