البحث الثنائي

البحث الثنائي (binary search) خوارزمية بحث فعّالة قائمة على استراتيجية التقسيم والتغلب. وهو يستفيد من الترتيب المرتَّب للبيانات ليقلّص نطاق البحث إلى النصف في كل جولة، حتى العثور على العنصر المستهدف أو أن يصبح مجال البحث فارغاً.

كما يوضح الشكل أدناه، نهيّئ أولاً المؤشرين $i = 0$ و$j = n - 1$، وهما يشيران إلى العنصرين الأول والأخير من المصفوفة على التوالي، ويمثّلان مجال البحث $[0, n - 1]$. لاحظ أن الأقواس المربعة تشير إلى مجال مغلق يشمل القيمتين الحديتين أنفسهما.

بعد ذلك، نفّذ الخطوتين التاليتين في حلقة:

1. احسب فهرس المنتصف $m = \lfloor {(i + j) / 2} \rfloor$، حيث يشير الرمز $\lfloor \: \rfloor$ إلى عملية التقريب نحو الأسفل.
2. قارن nums[m] بـtarget، وينتج عن ذلك ثلاث حالات:
   1. عندما يكون nums[m] < target، فهذا يعني أن target يقع في الفترة $[m + 1, j]$، لذا نفّذ $i = m + 1$.
   2. عندما يكون nums[m] > target، فهذا يعني أن target يقع في الفترة $[i, m - 1]$، لذا نفّذ $j = m - 1$.
   3. عندما يكون nums[m] = target، فهذا يعني أن target قد وُجد، لذا أعد الفهرس $m$.

إذا لم تحتوِ المصفوفة على العنصر المستهدف، فسيصبح مجال البحث فارغاً في النهاية. وفي هذه الحالة، أعد $-1$.

ومن الجدير بالذكر أنه بما أن $i$ و$j$ من النوع int، فإن $i + j$ قد يتجاوز نطاق النوع int. ولتجنّب تجاوز الأعداد الصحيحة الحد الأقصى، نستخدم عادةً الصيغة $m = \lfloor {i + (j - i) / 2} \rfloor$ لحساب نقطة المنتصف.

والشيفرة كما يلي:

/* البحث الثنائي (مجال مغلق من الطرفين) */
func binarySearch(nums []int, target int) int {
	// هيّئ المجال المغلق [0, n-1]، أي أن i وj يشيران إلى العنصرين الأول والأخير من المصفوفة
	i, j := 0, len(nums)-1
	// كرر، واخرج عندما يصبح مجال البحث فارغاً (يكون فارغاً عندما i > j)
	for i <= j {
		m := i + (j-i)/2      // احسب فهرس المنتصف m
		if nums[m] < target { // هذا يعني أن target يقع في الفترة [m+1, j]
			i = m + 1
		} else if nums[m] > target { // هذا يعني أن target يقع في الفترة [i, m-1]
			j = m - 1
		} else { // وُجد العنصر المستهدف، أعد فهرسه
			return m
		}
	}
	// لم يُعثر على العنصر المستهدف، أعد -1
	return -1
}

/* البحث الثنائي (مجال مغلق من الطرفين) */
function binarySearch(nums: number[], target: number): number {
    // هيّئ المجال المغلق [0, n-1]، أي أن i وj يشيران إلى العنصرين الأول والأخير من المصفوفة
    let i = 0,
        j = nums.length - 1;
    // كرر، واخرج عندما يصبح مجال البحث فارغاً (يكون فارغاً عندما i > j)
    while (i <= j) {
        // احسب فهرس المنتصف m
        const m = Math.floor(i + (j - i) / 2);
        if (nums[m] < target) {
            // هذا يعني أن target يقع في الفترة [m+1, j]
            i = m + 1;
        } else if (nums[m] > target) {
            // هذا يعني أن target يقع في الفترة [i, m-1]
            j = m - 1;
        } else {
            // وُجد العنصر المستهدف، أعد فهرسه
            return m;
        }
    }
    return -1; // لم يُعثر على العنصر المستهدف، أعد -1
}

التعقيد الزمني $O(\log n)$: في حلقة البحث الثنائي، يُقلَّص المجال إلى النصف في كل جولة، لذا يكون عدد التكرارات $\log_2 n$.

التعقيد المكاني $O(1)$: يستخدم المؤشران $i$ و$j$ مساحة ثابتة الحجم.

طرق تمثيل المجالات

بالإضافة إلى المجال المغلق المذكور أعلاه، ثمة تمثيل شائع آخر للمجال هو «مغلق من اليسار، مفتوح من اليمين»، ويُعرّف بـ $[0, n)$، أي أن الحد الأيسر مغلق بينما الحد الأيمن مفتوح. وفي ظل هذا التمثيل، يكون المجال $[i, j)$ فارغاً عندما $i = j$.

ويمكننا تنفيذ خوارزمية بحث ثنائي بالوظيفة نفسها استناداً إلى هذا التمثيل:

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

وبما أن الحدين الأيسر والأيمن في تمثيل «المجال المغلق» معرّفان كليهما كمغلقين، فإن عمليتي تقليص المجال عبر المؤشرين $i$ و$j$ متماثلتان أيضاً. وهذا يجعل الأخطاء أقل احتمالاً، لذا يُوصى عموماً بنهج «المجال المغلق».

المزايا والقيود

يقدّم البحث الثنائي أداءً جيداً في الزمن والمساحة كليهما.

• للبحث الثنائي كفاءة زمنية عالية. ومع أحجام البيانات الكبيرة، يحمل التعقيد الزمني اللوغاريتمي مزايا واضحة. فمثلاً، عندما يكون حجم البيانات $n = 2^{20}$، يتطلب البحث الخطي $2^{20} = 1048576$ تكراراً، بينما يحتاج البحث الثنائي إلى $\log_2 2^{20} = 20$ تكراراً فقط.
• لا يتطلب البحث الثنائي مساحة إضافية. فمقارنةً بخوارزميات البحث التي تحتاج مساحة إضافية (مثل البحث القائم على التجزئة)، يكون البحث الثنائي أكثر كفاءة في استهلاك المساحة.

غير أن البحث الثنائي لا يلائم جميع الحالات، ويرجع ذلك أساساً إلى الأسباب التالية:

• لا ينطبق البحث الثنائي إلا على البيانات المرتّبة. فإذا كانت بيانات الإدخال غير مرتّبة، فإن ترتيبها خصيصاً لاستخدام البحث الثنائي يكون بنتيجة عكسية، لأن خوارزميات الترتيب عادةً ما يكون تعقيدها الزمني $O(n \log n)$، وهو أعلى من تعقيد البحث الخطي والبحث الثنائي معاً. وفي السيناريوهات التي تتكرر فيها عمليات إدراج العناصر، يتطلب الحفاظ على ترتيب المصفوفة إدراج العناصر في مواضع محددة بتعقيد زمني $O(n)$، وهو مكلف جداً أيضاً.
• لا ينطبق البحث الثنائي إلا على المصفوفات. فالبحث الثنائي يتطلب وصولاً غير متصل وقافزاً إلى العناصر، وهذا النوع من الوصول غير فعّال في القوائم المترابطة، مما يجعله غير مناسب للقوائم المترابطة أو بنى البيانات القائمة عليها.
• مع أحجام البيانات الصغيرة، يكون أداء البحث الخطي أفضل. ففي البحث الخطي، تتطلب كل جولة عملية مقارنة واحدة فقط؛ بينما في البحث الثنائي، يتطلب الأمر عملية جمع واحدة وعملية قسمة واحدة و1-3 عمليات مقارنة وعملية جمع (أو طرح) واحدة، أي ما مجموعه 4-6 عمليات وحدة. لذلك، عندما يكون حجم البيانات $n$ صغيراً، يكون البحث الخطي في الواقع أسرع من البحث الثنائي.