البحث الثنائي في المصفوفات المدورة وغير المرتبة

ما المصفوفة المرتبة المدوّرة؟

# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossing

تحديد النصف المرتب

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1

تتبّع مثال

# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
    if nums[mid] == target:
        steps.append(f'Found at {mid}')
        break
    if nums[lo] <= nums[mid]:
        if nums[lo] <= target < nums[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    else:
        if nums[mid] < target <= nums[hi]:
            lo = mid + 1
        else:
            hi = mid - 1
for s in steps:
    print(s)

التعامل مع العناصر المكررة في التدوير

def search_rotated_with_dups(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return True
        # Ambiguous: shrink left boundary
        if nums[lo] == nums[mid] == nums[hi]:
            lo += 1
            hi -= 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return False

print(search_rotated_with_dups([1, 3, 1, 1, 1], 3))  # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0))  # True

العثور على أصغر عنصر في مصفوفة مرتبة مدورة

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1   # min is in right half
        else:
            hi = mid       # min is at mid or left of mid
    return nums[lo]

print(find_min([3, 4, 5, 1, 2]))   # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0
print(find_min([11, 13, 15, 17]))  # 11 (no rotation)

لماذا يكتشف arr[lo] <= arr[mid] أن النصف الأيسر مرتب

# Visualise: detect which half is sorted
examples = [
    ([4, 5, 6, 7, 0, 1, 2], 0, 6),  # mid=3, val=7 => left sorted
    ([6, 7, 0, 1, 2, 4, 5], 0, 6),  # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
    mid = lo + (hi - lo) // 2
    if arr[lo] <= arr[mid]:
        print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]}  => LEFT half sorted')
    else:
        print(f'arr[{lo}]={arr[lo]} >  arr[{mid}]={arr[mid]}  => RIGHT half sorted')

تحليل التعقيد

شرح تطبيقي للمسألة LeetCode 33

# LeetCode 33 — complete solution
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:        # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                            # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

# Tests
print(search([4,5,6,7,0,1,2], 0))   # 4
print(search([4,5,6,7,0,1,2], 3))   # -1
print(search([1], 0))               # -1

LeetCode 153: العثور على الأصغر دون تكرار

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

print(findMin([3,4,5,1,2]))         # 1
print(findMin([4,5,6,7,0,1,2]))     # 0
print(findMin([11,13,15,17]))       # 11

عدد مرات التدوير وفهرس المحور

def search_via_pivot(nums, target):
    n = len(nums)
    # Find pivot (index of minimum)
    lo, hi = 0, n - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    pivot = lo
    # Binary search with offset
    lo, hi = 0, n - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        real_mid = (mid + pivot) % n
        if nums[real_mid] == target:
            return real_mid
        elif nums[real_mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(search_via_pivot([4,5,6,7,0,1,2], 0))  # 4

جمع الأجزاء كلها

اختبار سريع

مراجعة الدرس