الإعلام الآلي — الخوارزميات: خوارزمية البحث الثنائي — الأولى ثانوي — المنهاج الجزائري

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

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

مبدأ عمل البحث الثنائي

يعمل البحث الثنائي على مصفوفة مرتبة تصاعديا. الخوارزمية: نحدد مؤشرين: left (أول عنصر) و right (آخر عنصر). نحسب mid = (left + right)/2. إذا كان العنصر المطلوب يساوي المصفوفة[mid]، نعيد mid. إذا كان العنصر أصغر، نبحث في النصف الأيسر (right = mid – 1). إذا كان أكبر، نبحث في النصف الأيمن (left = mid + 1). نكرر حتى نجد العنصر أو يصبح left > right.

مثال

ابحث عن الرقم 7 في المصفوفة [1, 3, 5, 7, 9, 11, 13]. left=0, right=6, mid=3 (القيمة 7). العنصر 7 = 7، وجد في الموضع 3. (تم البحث في خطوة واحدة فقط!).

تحليل الأداء

في كل خطوة، تقلص الخوارزمية مساحة البحث إلى النصف. التعقيد الزمني: O(log n) مقارنة بـ O(n) للبحث الخطي. لمصفوفة من 1000 عنصر، يحتاج البحث الخطي إلى 1000 مقارنة في أسوأ الحالات، بينما البحث الثنائي يحتاج فقط إلى 10 مقارنات.

تمارين

تمرين 1: ابحث عن الرقم 4 في المصفوفة [1, 2, 4, 6, 8, 10] باستخدام خوارزمية البحث الثنائي.

تمرين 2: قارن بين البحث الخطي والبحث الثنائي من حيث السرعة والشرط الأساسي للتطبيق.

للمزيد: الخوارزميات الأساسية: البحث والترتيب و مفهوم الخوارزمية وخصائصها.