🔍
AI Sketch • متوسط⏱️ 17 دقيقة للقراءة
أنماط البحث الثنائي
البحث الثنائي الكلاسيكي - مراجعة سريعة
يؤدي البحث الثنائي إلى تقليل مساحة البحث إلى النصف في كل خطوة. في مصفوفة مرتبة من عناصر n، يتم العثور على هدف في وقت O(log n).
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
بسيطة - ولكن القوة الحقيقية للبحث الثنائي تذهب إلى ما هو أبعد من المصفوفات المصنفة.
مفهوم مساحة البحث
يعمل البحث الثنائي عندما يكون لديك حالة رتيبة عبر نطاق ما. لا يلزم وجود "المصفوفة" - فأنت تحتاج فقط إلى نطاق [lo, hi] ووظيفة تنقلب من False إلى True (أو العكس) عند بعض الحدود.
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- answer
🤯
تم نشر البحث الثنائي لأول مرة في عام 1946، ولكن لم تتم كتابة أول نسخة خالية من الأخطاء حتى عام 1962 - 16 عامًا من الأخطاء المتتالية!
البحث الثنائي عن الإجابة
بدلاً من البحث في مصفوفة، ابحث في مساحة الإجابة. اسأل: "هل يمكنني تحقيق النتيجة X؟" إذا كانت الإجابة بنعم، حاول أصغر. إذا كان الجواب لا، حاول أكبر.
مثال: كوكو تأكل الموز
لدى كوكو n أكوام من الموز وh ساعة. ابحث عن الحد الأدنى لسرعة تناول الطعام حتى تنتهي في الوقت المناسب.
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid # speed works, try slower
else:
lo = mid + 1 # too slow, go faster
return lo
مساحة الإجابة هي [1, max(piles)] والحالة رتيبة - السرعة الأعلى تعني دائمًا ساعات أقل.
الدرس 7 من 100٪ مكتمل
مناقشة
تسجيل الدخول للانضمام إلى النقاش