البحث الثنائي والخوارزميات الجشعة

البحث الثنائي يقلص مساحة البحث للنصف في كل خطوة. الخوارزميات الجشعة تتخذ قرارات محلية مثلى. كلاهما فعال ويُختبر كثيرًا.

البحث الثنائي (Binary Search)

يعمل البحث الثنائي على بيانات مرتبة ويعمل بتعقيد O(log n) -- تحسن هائل مقارنة بالبحث الخطي O(n).

البحث الثنائي القياسي

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # تجنب الفيضان
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

أشكال البحث الثنائي

# إيجاد أول ظهور (الأقصى يسارًا)
def find_first(nums, target):
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1  # استمر بالبحث يسارًا
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

# البحث في مصفوفة مرتبة مُدوّرة
def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        # النصف الأيسر مرتب
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # النصف الأيمن مرتب
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

البحث الثنائي على مساحة الإجابات (رائج في 2026)

بدلاً من البحث في مصفوفة مرتبة، تبحث في مساحة الإجابات -- نطاق الإجابات الممكنة.

# كوكو تأكل الموز: تقليل سرعة الأكل
def min_eating_speed(piles, h):
    import math

    def can_finish(speed):
        return sum(math.ceil(p / speed) for p in piles) <= h

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid  # جرّب أبطأ
        else:
            left = mid + 1  # يجب أن تكون أسرع
    return left

# تقسيم مصفوفة لأكبر مجموع: تقليل الحد الأقصى
def split_array(nums, k):
    def can_split(max_sum):
        count, current = 1, 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = num
            else:
                current += num
        return count <= k

    left, right = max(nums), sum(nums)
    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid
        else:
            left = mid + 1
    return left

التعرف على النمط: عندما تطلب المسألة "تقليل الحد الأقصى" أو "تكبير الحد الأدنى"، فكّر في البحث الثنائي على مساحة الإجابات.

الخوارزميات الجشعة (Greedy)

الخوارزميات الجشعة تتخذ القرار المحلي الأمثل في كل خطوة، أملاً في الوصول للحل الأمثل العام. تعمل عندما تمتلك المسألة خاصية الاختيار الجشع.

مسائل جشعة كلاسيكية

# لعبة القفز: هل يمكنك الوصول للفهرس الأخير؟
def can_jump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True

# جدولة الفترات: أقصى فترات غير متداخلة
def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])  # ترتيب حسب وقت النهاية
    count = 0
    end = float('-inf')
    for start, finish in intervals:
        if start >= end:
            end = finish  # خذ هذه الفترة
        else:
            count += 1  # تخطّ (تداخل)
    return count

متى يعمل الجشع ومتى لا يعمل

يعمل (الجشع مناسب)	لا يعمل (تحتاج DP)
اختيار الأنشطة	حقيبة الظهر 0/1
ترميز Huffman	أطول سلسلة فرعية مشتركة
الحقيبة الكسرية	ضرب سلسلة المصفوفات
لعبة القفز	مسافة التعديل
دمج الفترات	تغيير العملات (فئات عشوائية)

نصيحة للمقابلات: إذا أعطى الحل الجشع إجابة خاطئة على مثال صغير، فأنت على الأرجح تحتاج للبرمجة الديناميكية بدلاً من ذلك.

---

التالي: DFS و BFS والتراجع -- أنماط لاستكشاف جميع الاحتمالات. :::