الخوارزميات: خوارزمية البحث الثنائي (Binary Search) – الإعلام الآلي — السنة الأولى ثانوي (جذع مشترك علوم وتكنولوجيا) — المنهاج الجزائري

الخوارزميات: خوارزمية البحث الثنائي (Binary Search)

البحث الثنائي (Binary Search) هو خوارزمية فعالة للبحث في مصفوفة مرتبة. هذا الدرس لتلاميذ السنة الأولى ثانوي جذع مشترك علوم وتكنولوجيا.

مبدأ الخوارزمية

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

الخوارزمية خطوة بخطوة

1. نحدد الحد الأيسر L = 0 والحد الأيمن R = n-1
2. نحسب المنتصف M = (L+R)/2
3. إذا كان العنصر في المنتصف = المطلوب، نعيد M
4. إذا كان المطلوب < العنصر في المنتصف، نبحث في النصف الأيسر R = M-1
5. إذا كان المطلوب > العنصر في المنتصف، نبحث في النصف الأيمن L = M+1
6. نكرر حتى نجد العنصر أو يصبح L > R

التعقيد الزمني

البحث الثنائي: O(log n) مقابل O(n) للبحث الخطي. لمصفوفة من مليون عنصر، يكفي 20 خطوة فقط!

تمارين

تمرين 1: ابحث عن الرقم 7 في المصفوفة [1,3,5,7,9,11,13] باستخدام البحث الثنائي.
تمرين 2: كم خطوة يحتاجها البحث الثنائي للبحث في مصفوفة من 1024 عنصراً؟
تمرين 3: قارن بين البحث الثنائي والبحث الخطي من حيث السرعة.

مقدمة في الخوارزميات ← راجع درس الخوارزميات

خوارزميات الترتيب ← راجع درس خوارزميات الترتيب