الدرس: الخوارزميات البحث الثنائي — الإعلام الآلي — الثالثة ثانوي (شعب علمية) — بكالوريا — المنهاج الجزائري

الخوارزميات: البحث الثنائي

البحث الثنائي (Binary Search) هو خوارزمية فعالة للبحث عن عنصر في مصفوفة مرتبة. تعمل بقسمة المصفوفة إلى نصفين في كل خطوة، مما يجعل تعقيدها الزمني O(log n). هذا أفضل بكثير من البحث الخطي O(n).

1. مبدأ العمل

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

2. تطبيق في بايثون

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left+right)//2
        if arr[mid]==target: return mid
        elif arr[mid]<target: left=mid+1
        else: right=mid-1
    return -1

3. مثال تطبيقي

للبحث عن 19 في المصفوفة [3,7,11,15,19,23,27,31]:
left=0, right=7, mid=3 → arr[3]=15<19 → left=4
mid=5 → arr[5]=23>19 → right=4
mid=4 → arr[4]=19 → تم العثور في الفهرس 4.

4. شروط التطبيق

– يجب أن تكون المصفوفة مرتبة ترتيباً تصاعدياً أو تنازلياً.
– يجب أن يكون الوصول إلى العناصر عشوائياً (وليس تسلسلياً).
– مناسبة للمصفوفات الكبيرة حيث تظهر فعاليتها مقارنة بالبحث الخطي.

تمارين

1. طبق البحث الثنائي على [2,5,8,12,16,23,38,45,56,72] للبحث عن 45.
2. اشرح لماذا لا يعمل البحث الثنائي على مصفوفة غير مرتبة.
3. قارن بين التعقيد الزمني للبحث الثنائي والبحث الخطي.

دروس مشابهة

• خوارزميات الترتيب والفرز
• المصفوفات في بايثون