استراتيجية البحث بالتقسيم والتغلب

لقد تعلّمنا بالفعل أن خوارزميات البحث تنقسم إلى فئتين رئيسيتين.

• البحث بالقوة الغاشمة: يُنفَّذ باجتياز بنية البيانات، وتعقيده الزمني $O(n)$.
• البحث التكيّفي: يستفيد من تنظيم معيّن للبيانات أو من معلومات مسبقة، ويصل تعقيده الزمني إلى $O(\log n)$ أو حتى $O(1)$.

في الواقع، خوارزميات البحث ذات التعقيد الزمني $O(\log n)$ تُنفَّذ عادةً استناداً إلى استراتيجية التقسيم والتغلب، مثل البحث الثنائي والأشجار.

• كل خطوة من خطوات البحث الثنائي تقسّم المسألة (البحث عن عنصر هدف في مصفوفة) إلى مسألة أصغر (البحث عن العنصر الهدف في نصف المصفوفة)، وتستمر حتى تصبح المصفوفة فارغة أو يُعثر على العنصر الهدف.
• الأشجار نموذج يمثّل فكرة التقسيم والتغلب. ففي بنى البيانات مثل أشجار البحث الثنائية وأشجار AVL والأكوام، يكون التعقيد الزمني لمختلف العمليات $O(\log n)$.

استراتيجية التقسيم والتغلب في البحث الثنائي كما يلي.

• المسألة قابلة للتفكيك: يفكّك البحث الثنائي تعاودياً المسألة الأصلية (البحث في مصفوفة) إلى مسائل فرعية (البحث في نصف المصفوفة)، ويتحقق ذلك بمقارنة العنصر الأوسط بالعنصر الهدف.
• المسائل الفرعية مستقلة: في البحث الثنائي، لا تعالج كل جولة إلا مسألة فرعية واحدة، لا تتأثر بالمسائل الفرعية الأخرى.
• لا حاجة إلى دمج حلول المسائل الفرعية: يهدف البحث الثنائي إلى إيجاد عنصر محدد، لذا لا حاجة إلى دمج حلول المسائل الفرعية. وعندما تُحلّ مسألة فرعية، تكون المسألة الأصلية قد حُلّت أيضاً.

يمكن للتقسيم والتغلب أن يحسّن كفاءة البحث، لأن البحث بالقوة الغاشمة لا يستطيع استبعاد إلا خيار واحد في كل جولة، بينما يستطيع البحث بالتقسيم والتغلب استبعاد نصف الخيارات في كل جولة.

تنفيذ البحث الثنائي استناداً إلى التقسيم والتغلب

نُفِّذ البحث الثنائي في الأقسام السابقة استناداً إلى التكرار. والآن ننفّذه استناداً إلى التقسيم والتغلب (التعاود).

من منظور التقسيم والتغلب، نرمز للمسألة الفرعية المقابلة لمجال البحث $[i, j]$ بالرمز $f(i, j)$.

انطلاقاً من المسألة الأصلية $f(0, n-1)$، نفّذ البحث الثنائي عبر الخطوات التالية.

1. احسب نقطة المنتصف $m$ لمجال البحث $[i, j]$، واستخدمها لاستبعاد نصف مجال البحث.
2. حلّ تعاودياً المسألة الفرعية المنخفضة إلى النصف، والتي قد تكون $f(i, m-1)$ أو $f(m+1, j)$.
3. كرر الخطوتين 1. و2. حتى يُعثر على target، أو عُد عندما يصبح المجال فارغاً.

يوضح الشكل أدناه عملية التقسيم والتغلب في البحث الثنائي عن العنصر $6$ في مصفوفة.

في شيفرة التنفيذ، نعرّف دالة تعاودية dfs() لحل المسألة $f(i, j)$:

/* البحث الثنائي */
func binarySearch(nums []int, target int) int {
	n := len(nums)
	return dfs(nums, target, 0, n-1)
}

/* البحث الثنائي */
function binarySearch(nums: number[], target: number): number {
    const n = nums.length;
    // حل المسألة f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}