المستوى: مبتدئ — المقال ده مكتوب لحد لسه بادئ في الخوارزميات. كل مفهوم هتلاقيه متشرح بمثال بسيط الأول، وبعدها بشكل علمي دقيق. وقت القراءة المتوقع حوالي 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