الدرس 6 · الوحدة 3: تصميم وتنفيذ خوارزميات فعّالة

فرّق تسُد: البحث الثنائي

كيف تجد رقمًا بين مليار رقم في 30 خطوة فقط؟ ⏱ نحو 30 دقيقة.

بعد هذا الدرس ستستطيع أن:

تشرح أسلوب فرّق تسُد بخطواته الثلاث.
تنفذ البحث الثنائي بحلقة وبالعودية.
تفسّر لماذا يحتاج البحث الثنائي نحو log₂ n خطوة.
تعرف شرط الترتيب وتستخدم bisect.

١فرّق تسُد

فرّق تسُد Divide and Conquer: أسلوب لتصميم الخوارزميات من ثلاث خطوات:

الخطوة	معناها
فرّق Divide	اقسم المسألة إلى مسائل أصغر من النوع نفسه.
سُد Conquer	حل المسائل الصغيرة (غالبًا بالعودية).
اجمع Combine	ركّب حلولها لتحصل على حل المسألة الكبيرة.

وأشهر أمثلته: البحث الثنائي (هذا الدرس)، والترتيب بالدمج والترتيب السريع (الدرس القادم).

٢لعبة: خمّن الرقم

فكّر صديقك في رقم بين 1 و 100، ويقول لك بعد كل تخمين: «أكبر» أو «أصغر». أذكى استراتيجية: خمّن الوسط دائمًا. 50؟ «أكبر». 75؟ «أصغر». 62؟ … في كل تخمين تستبعد نصف الاحتمالات الباقية، فتجد أي رقم في 7 تخمينات على الأكثر.

البحث الثنائي Binary Search يطبّق الفكرة نفسها على قائمة مرتبة:

🎬 محاكاة: البحث الثنائي

السرعة

مقارنةتبديل أو نقلالمحور أو الوسطفي مكانه النهائي أو وُجد

٣الكود

main.py

def binary_search(a, x):    lo, hi = 0, len(a) - 1    while lo <= hi:        mid = (lo + hi) // 2        if a[mid] == x:            return mid           # وُجد: نُرجع موقعه        elif a[mid] < x:            lo = mid + 1         # نستبعد النصف الأيسر        else:            hi = mid - 1         # نستبعد النصف الأيمن    return -1                    # غير موجود a = [3, 8, 12, 17, 21, 26, 30, 35, 41, 47]print(binary_search(a, 30))print(binary_search(a, 5))

Shell×

>>> %Run main.py

-1

>>>

وبالعودية، مباشرة من فكرة فرّق تسُد:

main.py

def bsearch(a, x, lo, hi):    if lo > hi:        return -1                        # حالة توقف: المجال فارغ    mid = (lo + hi) // 2    if a[mid] == x:        return mid                       # حالة توقف: وجدناه    if a[mid] < x:        return bsearch(a, x, mid + 1, hi)    # النصف الأيمن    return bsearch(a, x, lo, mid - 1)        # النصف الأيسر a = [3, 8, 12, 17, 21, 26, 30, 35, 41, 47]print(bsearch(a, 41, 0, len(a) - 1))

Shell×

>>> %Run main.py

>>>

٤كم خطوة يحتاج؟

في كل خطوة ينقسم المجال نصفين. فعدد الخطوات هو: كم مرة نقسم n على 2 حتى نصل إلى 1؟ وهذا هو اللوغاريتم للأساس 2: log₂ n.

main.py

import math for n in [16, 1000, 1000000, 1000000000]:    linear = n    binary = math.floor(math.log2(n)) + 1    print(f"{n:>13,} عنصر | خطي: {linear:>13,} | ثنائي: {binary}")

Shell×

>>> %Run main.py

16 عنصر | خطي: 16 | ثنائي: 5

1,000 عنصر | خطي: 1,000 | ثنائي: 10

1,000,000 عنصر | خطي: 1,000,000 | ثنائي: 20

1,000,000,000 عنصر | خطي: 1,000,000,000 | ثنائي: 30

>>>

مليار عنصر: البحث الخطي قد يحتاج مليار مقارنة، والثنائي 30 فقط. هذا معنى «الخوارزمية الفعّالة».

٥الشرط المهم: الترتيب

البحث الثنائي يعمل على قائمة مرتبة فقط؛ لأنه يستنتج من مقارنة واحدة أي نصف يستبعد. على قائمة غير مرتبة قد يستبعد النصف الذي فيه العنصر:

main.py

def binary_search(a, x):    lo, hi = 0, len(a) - 1    while lo <= hi:        mid = (lo + hi) // 2        if a[mid] == x:            return mid        elif a[mid] < x:            lo = mid + 1        else:            hi = mid - 1    return -1 print(binary_search([40, 5, 30, 10, 20], 5))   # 5 موجودة!

Shell×

>>> %Run main.py

-1

>>>

وفي بايثون مكتبة جاهزة للبحث الثنائي اسمها bisect:

main.py

import bisecta = [3, 8, 12, 17, 21, 26]i = bisect.bisect_left(a, 17)print(i, a[i] == 17)

Shell×

>>> %Run main.py

3 True

>>>

توقّع وتحقّق

شرط البحث الثنائي:

ليعرف أي نصف يستبعد.

أقصى عدد خطوات للبحث الثنائي في 1024 عنصرًا تقريبًا:

log₂ 1024 = 10، والخطوة الأخيرة.

إن كان a[mid] أصغر من x:

نذهب إلى النصف الأيمن.

خطوات فرّق تسُد:

Divide, Conquer, Combine.

الخلاصة

فرّق تسُد: قسّم، ثم حل الأجزاء، ثم اجمع الحلول.
البحث الثنائي: انظر إلى الوسط، واستبعد نصف القائمة في كل خطوة.
عدد الخطوات نحو log₂ n: مليار عنصر في 30 خطوة.
يعمل على القوائم المرتبة فقط، ومكتبته الجاهزة bisect.

تحدٍّ برمجي: عدّاد خطوات البحث الثنائي

متوسط

عدّل البحث الثنائي ليُرجع الموقع وعدد المقارنات معًا، ثم ابحث في الأعداد الزوجية من 2 إلى 2000.

المطلوب:

الدالة تُرجع (الموقع، عدد المقارنات).
ابحث عن 1000 ثم عن 1999 (غير موجود).
اطبع لكل بحث: الموقع: … المقارنات: …

ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:

main.py

a = list(range(2, 2001, 2)) def binary_search(a, x):    pass

المطلوب×

الموقع: 499 المقارنات: 1

الموقع: -1 المقارنات: 10

💡 تلميح 1

زد العدّاد مرة في كل دورة من الحلقة.

💡 تلميح 2

return mid, steps تُرجع قيمتين معًا.

حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.

main.py

a = list(range(2, 2001, 2)) def binary_search(a, x):    lo, hi = 0, len(a) - 1    steps = 0    while lo <= hi:        mid = (lo + hi) // 2        steps += 1        if a[mid] == x:            return mid, steps        elif a[mid] < x:            lo = mid + 1        else:            hi = mid - 1    return -1, steps for x in [1000, 1999]:    pos, steps = binary_search(a, x)    print("الموقع:", pos, "المقارنات:", steps)

انتقل إلى تقييم الدرساختيار من متعدد، وصح وخطأ، وأكمل الفراغ، وتتبّع الناتج.ابدأ التقييم ←

📝 معلم؟ أرسل ملاحظة للمؤلف عن هذا الدرس