27. البحث الثنائي (Binary Search): المتطلبات والتطبيق (O(log N))

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

المفهوم

يقوم البحث الثنائي بإزالة نصف مساحة البحث المتبقية في كل خطوة. وهو يعمل عن طريق التحقق من العنصر الأوسط للنطاق الحالي.

1. مقارنة القيمة الهدف بالعنصر الأوسط.
2. إذا تطابقا، إرجاع الفهرس الأوسط.
3. إذا كان الهدف أصغر، الانتقال إلى النصف الأيسر.
4. إذا كان الهدف أكبر، الانتقال إلى النصف الأيمن.

التطبيق (التكراري)

python def binary_search(arr, target): low = 0 high = len(arr) - 1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1  # Search right half
    else:
        high = mid - 1 # Search left half
return -1

الكفاءة: O(log N)