البحث الثنائي الكلاسيكي: اليسار واليمين والوسط
نفّذ البحث الثنائي تكراريًا وبصورة ذاتية، وأتقن تفاصيل تجاوز الحدود الخاصة بحدود lo وhi، وتحقق من الصحة باستخدام مدخلات الحالات الحدية
البحث الثنائي الكلاسيكي: اليسار واليمين والوسط درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
أهمية البحث الثنائي
يخفض البحث الثنائي البحث الخطي ذي التعقيد O(n) إلى O(log n) عبر تقسيم مساحة البحث إلى النصف في كل خطوة. ففي مصفوفة تضم مليون عنصر، قد يتطلب البحث الخطي ما يصل إلى 1,000,000 مقارنة، بينما يحتاج البحث الثنائي إلى 20 مقارنة على الأكثر. تجعل هذه الكفاءة البحث الثنائي إحدى أكثر الخوارزميات شيوعًا في اختبارات مقابلات البرمجة.
تتمثل الفكرة الأساسية في أن المصفوفة المرتبة تتيح لكم، بعد مقارنة واحدة، تحديد أي نصف من البيانات المتبقية يمكن استبعاده بالكامل.
إطار اليسار والمنتصف واليمين
يستخدم البحث الثنائي ثلاثة مؤشرات للفهرسة: lo (الحد الأيسر)، وhi (الحد الأيمن)، وmid (نقطة المنتصف). في كل تكرار تحسبون mid = (lo + hi) // 2 وتقارنون الهدف بالعنصر arr[mid]. إذا كان الهدف أصغر، فحرّكوا hi = mid - 1؛ وإذا كان أكبر، فحرّكوا lo = mid + 1؛ وإذا كان مساويًا، فقد عثرتم عليه.
تستمر الحلقة ما دام lo <= hi. وعند خروج الحلقة من دون العثور على الهدف، أعيدوا -1.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6)) # -1تجنب تجاوز سعة العدد الصحيح في mid
قد يسبب التعبير mid = (lo + hi) // 2 تجاوزًا لسعة العدد الصحيح في اللغات التي تستخدم أعدادًا صحيحة ثابتة العرض (Java وC++). أما أعداد Python فذات دقة اعتباطية، لذلك لا يحدث التجاوز مطلقًا، لكن المقابلين يتوقعون منكم معرفة البديل الآمن: mid = lo + (hi - lo) // 2.
يحسب هذا الشكل نقطة المنتصف نفسها، لكنه يضيف نصف المسافة فقط إلى lo بدلًا من جمع المؤشرين أولًا. إن ذكر ذلك في المقابلة يدل على وعيكم بالاعتبارات منخفضة المستوى.
# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2 # fine in Python
mid_safe = lo + (hi - lo) // 2 # same result, no overflow risk
print(mid_unsafe == mid_safe) # Trueالحدود الشاملة مقابل الحدود الحصرية
من أصعب جوانب البحث الثنائي اختيار ما إذا كان hi يشير إلى آخر فهرس صالح (حد شامل، hi = len(arr) - 1) أو إلى الموضع الواقع بعد النهاية (حد حصري، hi = len(arr)). تتطلب الاصطلاحات المختلفة شروطًا مختلفة للحلقة وتحديثات مختلفة للحدود.
مع الحدود الشاملة استخدموا while lo <= hi وحدّثوا hi = mid - 1. ومع الحدود الحصرية استخدموا while lo < hi وحدّثوا hi = mid. إن خلط الاصطلاحين هو المصدر الأكثر شيوعًا للأخطاء في تطبيقات البحث الثنائي.
# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
lo, hi = 0, len(arr) # hi is one past last
while lo < hi: # strictly less than
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # NOT mid - 1
return lo if lo < len(arr) and arr[lo] == target else -1
print(search_exclusive([2, 4, 6, 8, 10], 6)) # 2البحث الثنائي باستخدام الاستدعاء الذاتي
يمكن كتابة البحث الثنائي باستخدام الاستدعاء الذاتي عبر تمرير حدود lo وhi المحدَّثة عبر مكدس الاستدعاءات. تقلص كل استدعاء ذاتي مساحة البحث إلى النصف، ولذلك يكون العمق O(log n). حالة الأساس هي عندما يكون lo > hi (لم يُعثر على الهدف) أو عندما يكون arr[mid] == target (عُثر عليه).
يُفضَّل الإصدار التكراري في كود الإنتاج لأنه يتجنب الحمل الإضافي لإطارات مكدس الاستدعاءات، لكن الإصدار القائم على الاستدعاء الذاتي يوضح بنية التقسيم والحل بصورة أكبر على السبورة.
def binary_search_rec(arr, target, lo, hi):
if lo > hi:
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, hi)
else:
return binary_search_rec(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1)) # 4حالات الحافة: مصفوفة فارغة وعنصر واحد
يجب أن يتعامل البحث الثنائي الموثوق مع حالات الحافة دون أن يتعطل. الحالات الثلاث الأكثر شيوعًا هي: مصفوفة فارغة (لا تُنفَّذ الحلقة مطلقًا وتُعاد القيمة -1 بشكل صحيح)، ومصفوفة تحتوي على عنصر واحد (تتساوى mid وlo وhi، وتكفي مقارنة واحدة)، وأهداف خارج النطاق (يتجاوز lo قيمة hi في النهاية وتُعاد القيمة -1).
احرصوا دائمًا على التحقق من تطبيقكم باستخدام هذه المدخلات قبل الانتقال إلى أسئلة المتابعة في المقابلة.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(binary_search([], 5)) # -1 (empty)
print(binary_search([7], 7)) # 0 (single, found)
print(binary_search([7], 3)) # -1 (single, not found)
print(binary_search([1,3,5], 0)) # -1 (below range)
print(binary_search([1,3,5], 9)) # -1 (above range)التعقيد الزمني وتعقيد المساحة
يبلغ التعقيد الزمني للبحث الثنائي O(log n) لأن كل مقارنة تقسم مساحة البحث إلى النصف. بعد k من المقارنات تصبح المساحة المتبقية n/2^k؛ وينتهي البحث عندما تصل هذه القيمة إلى 1، ولذلك k = log₂ n.
يبلغ تعقيد المساحة O(1) في الإصدار التكراري (ثلاثة متغيرات صحيحة فقط)، وO(log n) في الإصدار القائم على الاستدعاء الذاتي بسبب عمق مكدس الاستدعاءات. اذكروا التعقيدين دائمًا في المقابلة، وفضّلوا الإصدار التكراري عندما تكون المساحة محدودة.
import math
for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
steps = math.ceil(math.log2(n + 1))
print(f'n={n:>12,} max comparisons={steps}')البحث عن تطابق تام مقابل حد
يعيد البحث الثنائي الكلاسيكي أي فهرس يوجد فيه الهدف. لكن كثيرًا من مسائل المقابلات تطلب أول ظهور للهدف أو آخر ظهور له. في هذه الحالة يجب متابعة البحث حتى بعد العثور على تطابق — فبدلًا من العودة فورًا، ضيّقوا الحد واستمروا.
عند البحث عن الظهور الأول، وبعد العثور على arr[mid] == target، سجّلوا mid كمرشح واضبطوا hi = mid - 1. وللعثور على الظهور الأخير اضبطوا lo = mid + 1.
def first_occurrence(arr, target):
lo, hi, result = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
result = mid
hi = mid - 1 # keep searching left
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return result
print(first_occurrence([1, 2, 2, 2, 3], 2)) # 1استخدام الوحدة bisect في Python
توفر المكتبة القياسية في Python الدالتين bisect.bisect_left(arr, x) وbisect.bisect_right(arr, x) لإجراء بحث ثنائي جاهز للاستخدام في الإنتاج. تعيد bisect_left الفهرس الموجود في أقصى اليسار الذي يمكن إدراج x فيه مع الحفاظ على ترتيب المصفوفة، وبذلك تعثر فعليًا على أول موضع يحقق arr[i] >= x.
قد يسمح لكم المقابلون باستخدام bisect؛ فتأكدوا دائمًا أولًا. ومع ذلك، تظل معرفة آلية عملها داخليًا (فهي تطبق بحثًا ثنائيًا بتعقيد O(log n)) أمرًا أساسيًا.
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2)) # 1 (first 2)
print(bisect.bisect_right(arr, 2)) # 4 (after last 2)
# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target) # Trueالأخطاء الشائعة في البحث الثنائي
تسبب ثلاثة أخطاء معظم مشكلات البحث الثنائي في المقابلات. أولًا، شرط الحلقة الخاطئ: يؤدي استخدام < بدلًا من <= مع الحدود الشاملة إلى تخطي العنصر الأخير المتبقي. ثانيًا، التحديث غير الصحيح للحدود: يؤدي نسيان +1 أو -1 إلى حلقة لا نهائية عندما يكون lo == hi. ثالثًا، العمل على مصفوفة غير مرتبة: لا يكون البحث الثنائي صحيحًا إلا مع البيانات المرتبة.
قبل كتابة أي بحث ثنائي، اذكروا بصوت عالٍ: «المصفوفة مرتبة، وحدودي شاملة، وتعمل حلقَتي ما دام lo <= hi.»
# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi: # should be lo <= hi for exact-match
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # stops, but never returns mid when found
return lo if arr[lo] == target else -1
print(buggy([1, 3, 5, 7], 7)) # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1)) # 0 (correct)
print(buggy([1, 3, 5, 7], 4)) # -1 (correct)نصائح للمقابلة حول البحث الثنائي
عندما تواجهون مسألة تتعلق بـمصفوفة مرتبة، أو دالة متزايدة رتيبًا، أو مساحة بحث يمكن تقسيمها إلى النصف، ففكروا فورًا في البحث الثنائي. في المقابلة، اشرحوا طريقة تفكيركم: «بما أن المصفوفة مرتبة، يمكنني استبعاد نصف العناصر في كل مقارنة، ما يعطي O(log n).»
تحققوا دائمًا من الحل باستخدام ثلاثة مدخلات على الأقل: قيمة في البداية، وقيمة في النهاية، وقيمة غير موجودة. إن ذكر التعقيد مسبقًا — «الزمن O(log n)، والمساحة O(1)» — قبل أن يُطلب منكم ذلك يدل على امتلاككم أساسيات قوية.
اختبار سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
مراجعة الدرس
في هذا الدرس تعلمتم أن: البحث الثنائي يقسم مساحة البحث إلى النصف في كل خطوة، محققًا زمنًا قدره O(log n)، وأن اصطلاح الحدود الشاملة يستخدم lo <= hi مع التحديثين lo = mid+1 وhi = mid-1، وأن العثور على الظهور الأول أو الأخير يتطلب متابعة البحث بعد العثور على تطابق بدلًا من العودة فورًا. في الدرس التالي سنستكشف كيفية توسيع البحث الثنائي ليعمل مع المصفوفات المدوّرة وغير المرتبة.
الأسئلة الشائعة
هل درس «البحث الثنائي الكلاسيكي: اليسار واليمين والوسط» مجاني؟
نعم — نص درس «البحث الثنائي الكلاسيكي: اليسار واليمين والوسط» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «البحث الثنائي الكلاسيكي: اليسار واليمين والوسط»؟
نفّذ البحث الثنائي تكراريًا وبصورة ذاتية، وأتقن تفاصيل تجاوز الحدود الخاصة بحدود lo وhi، وتحقق من الصحة باستخدام مدخلات الحالات الحدية تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «البحث الثنائي الكلاسيكي: اليسار واليمين والوسط»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- البحث الثنائي الكلاسيكي: اليسار واليمين والوسط
- البحث الثنائي في المصفوفات المدورة وغير المرتبة
- الحد الأدنى والحد الأعلى
- البحث الثنائي في فضاء الإجابات