البحث الثنائي
إذا احتوت المصفوفة على قيم غير مرتّبة فإنّ البحث الخطي هو أفضل ما يمكن القيام به للعثور على قيمة معينة، ولكن إن كانت العناصر في المصفوفة مرتّبة ترتيبًا تصاعديًا، فيمكن تسريع عملية البحث، وذلك باستخدام طريقة البحث الثنائي Binary Search.
تبدأ عملية البحث الثنائي بالتحقق من القيمة الموجودة في منتصف المصفوفة (سنسمّي هذا الموقع mid وقيمة العنصر الموجود في هذا الموقع kmid). فإن كانت kmid=K تتوقف عملية البحث مباشرة، وهذا نادر الحدوث.
إن معرفة قيمة العنصر الموجود في منتصف المصفوفة مفيد للغاية وسيساعد في توجيه عملية البحث نحو الطريق الصحيح. فإن كانت kmid>K فإنّنا سنجزم بعدم إمكانية ظهور K في أي موقع أكبر من موقع mid، وبهذا يمكن تجاهل النصف العلوي من المصفوفة في عمليات البحث التالية.
وإن كانت kmid<K فإنّنا سنجزم بعدم إمكانية ظهور K في أي موقع أصغر من موقع mid، وبهذا يمكن تجاهل النصف السفلي من المصفوفة في عمليات البحث التالية.
وبطبيعة الحال فإنّ نصف المواقع في المصفوفة ستستبعد من عملية البحث في كلا الحالتين.
بعد ذلك تتحقّق عملية البحث الثنائي من القيمة الموجودة في منتصف الجزء الذي يتوقّع أن تكون القيمة المطلوبة موجودة فيه، وبذلك يمكن استبعاد نصف المواقع المتبقية من عمليات البحث التالية.
تستمر عملية البحث الثنائي بهذا الأسلوب إلى أن تعثر على العنصر المطلوب أو إلى حين الفراغ من جميع المواقع الموجودة في المصفوفة والتي يمكن أن تحتوي على قيمة K.
تنفيذ الخوارزمية
يمكن تنفيذ خوارزمية البحث الثنائي بطريقتين: التعاودية Recursion والتكرارية Iteration.
الطريقة التعاودية
تعرض الأمثلة التالية طريقة تنفيذ خوارزمية البحث الثنائي تعاوديًا وفي عدد من لغات البرمجة:
- C++:
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// إن كان العنصر الموجود في وسط المصفوفة هو نفسه العنصر المعطى
// فسنعيد العنصر نفسه
if (arr[mid] == x)
return mid;
// إن كان العنصر أصغر من العنصر الموجود في وسط المصفوفة
// فإنه سيكون موجودًا في النصف الأيسر من المصفوفة قطعًا
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// وإلا فإنّ العنصر سيكون موجودًا في النصف الأيمن من المصفوفة قطعًا
return binarySearch(arr, mid + 1, r, x);
}
// إن وصلنا إلى هنا فهذا يعني
// أن العنصر غير موجود في المصفوفة
return -1;
}
// اختبار الدالة السابقة
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
- بايثون:
def binarySearch (arr, l, r, x):
# التحقق من الحالة الأساس
if r >= l:
mid = l + (r - l)/2
# إن كان العنصر المعطى موجودًا في وسط المصفوفة فسنعيد العنصر نفسه
if arr[mid] == x:
return mid
# إن كان العنصر المعطى أصغر من العنصر الموجود في وسط المصفوفة
# فإنه سيكون موجودًا في النصف الأيسر من المصفوفة قطعًا
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# وإلا فإنّ العنصر سيكون موجودًا في النصف الأيمن من المصفوفة قطعًا
else:
return binarySearch(arr, mid + 1, r, x)
else:
# العنصر غير موجود في المصفوفة
return -1
# اختبار الدالة السابقة
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print "Element is present at index % d" % result
else:
print "Element is not present in array"
- جافا:
class BinarySearch {
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// إن كان العنصر الموجود في وسط المصفوفة هو نفسه العنصر المعطى
// فسنعيد العنصر نفسه
if (arr[mid] == x)
return mid;
// إن كان العنصر أصغر من العنصر الموجود في وسط المصفوفة
// فإنه سيكون موجودًا في النصف الأيسر من المصفوفة قطعًا
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// وإلا فإنّ العنصر سيكون موجودًا في النصف الأيمن من المصفوفة قطعًا
return binarySearch(arr, mid + 1, r, x);
}
// إن وصلنا إلى هنا فهذا يعني أن العنصر المعطى غير موجود في المصفوفة
return -1;
}
// اختبار التابع السابق
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
الطريقة التكرارية
تعرض الأمثلة التالية طريقة تنفيذ خوارزمية البحث الثنائي تكراريًا وفي عدد من لغات البرمجة:
- C++:
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// التحقق من وجود القيمة المعطاة في وسط المصفوفة
if (arr[m] == x)
return m;
// تجاهل النصف الأيسر إن كانت القيمة المعطاة أكبر من القيمة الموجودة في وسط المصفوفة
if (arr[m] < x)
l = m + 1;
// تجاهل النصف الأيمن إن كانت القيمة المعطاة أصغر من القيمة الموجودة في وسط المصفوفة
else
r = m - 1;
}
// إن وصلنا إلى هنا فهذا يعني أنّ العنصر المعطى غير موجود في المصفوفة
return -1;
}
// اختبار الدالة السابقة
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
- بايثون:
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l)/2;
# التحقق من وجود القيمة المعطاة في وسط المصفوفة
if arr[mid] == x:
return mid
# تجاهل النصف الأيسر إن كانت القيمة المعطاة أكبر من القيمة الموجودة في وسط المصفوفة
elif arr[mid] < x:
l = mid + 1
# تجاهل النصف الأيمن إن كانت القيمة المعطاة أصغر من القيمة الموجودة في وسط المصفوفة
else:
r = mid - 1
# إن وصلنا إلى هنا فهذا يعني
# أن العنصر المعطى غير موجود في المصفوفة
return -1
# اختبار الدالة السابقة
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print "Element is present at index % d" % result
else:
print "Element is not present in array"
- جافا:
class BinarySearch {
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// التحقق من وجود القيمة المعطاة في وسط المصفوفة
if (arr[m] == x)
return m;
// تجاهل النصف الأيسر إن كانت القيمة المعطاة أكبر من القيمة الموجودة في وسط المصفوفة
if (arr[m] < x)
l = m + 1;
// تجاهل النصف الأيمن إن كانت القيمة المعطاة أصغر من القيمة الموجودة في وسط المصفوفة
else
r = m - 1;
}
// إن وصلنا إلى هنا فهذا يعني
// أن العنصر المطلوب غير موجود في المصفوفة
return -1;
}
// اختبار التابع السابق
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at "
+ "index " + result);
}
}
التعقيد الزمني
يبلغ التعقيد الزمني لعملية البحث الثنائي المقدار O(Logn)، وذلك لأنّ العملية تقسم المصفوفة إلى نصفين بصورة متكررة، وتتوقف (في أسوأ الحالات) عند الوصول إلى جزء من المصفوفة طوله 1، وليس بالإمكان سوى تقسيم المصفوفة إلى أنصاف logn مرّة قبل الوصول إلى 1.
أشكال أخرى من عملية البحث الثنائي
يمكن لعملية البحث الثنائي أن تصبح معقدة عند وجود عناصر مكرّرة في المصفوفة المرتبة، وعملية البحث الثنائي غير مقصورة على إيجاد العنصر أو عدمه في المصفوفة، ولكن هناك خمسة أشكال هي:
- وجود العنصر في المصفوفة (قيمة صحيحة أو خاطئة)
- موقع الظهور الأول للمفتاح المعطى
- موقع الظهور الأخير للمفتاح المعطى
- موقع أصغر عنصر يكون أكبر من المفتاح المعطى
- موقع أكبر عنصر يكون أصغر من المفتاح المعطى
تعتمد عمليات البحث هذه على الأساس المنطقي ذاته، ولكنّها تتضمن بعض الاختلافات في طريقة التنفيذ.
وجود العنصر في المصفوفة
تعطي طريقة البحث هذه نتيجة منطقية (True أو False) لوجود العنصر في المصفوفة:
Input : 2 3 3 5 5 5 6 6
Function : Contains(4)
Returns : False
Function : Contains(5)
Returns : True
يعرض المثال التالي طريقة تنفيذ عملية البحث هذه:
#include <bits/stdc++.h>
using namespace std;
int n = 8; // حجم المصفوفة
int a[] = { 2, 3, 3, 5, 5, 5, 6, 6 }; // مصفوفة مرتبة
/* البحث عن المفتاح المطلوب
* تعيد الدالة قيمة صحيحة إن كان المفتاح موجودًا في المصفوفة
* وتعيد قيمة خاطئة إن لم يكن المفتاح موجودًا
*/
bool contains(int low, int high, int key)
{
bool ans = false;
while (low <= high) {
int mid = low + (high - low) / 2;
int midVal = a[mid];
if (midVal < key) {
// إن كانت القيمة في وسط المصفوفة أصغر من المفتاح المعطى
// فإن جميع العناصر النصف الأيسر من المصفوفة هي كذلك أصغر من
// العنصر المعطى لذا نبدأ البحث في النصف الأيمن من المصفوفة
low = mid + 1;
}
else if (midVal > key) {
// إن كانت القيمة في وسط المصفوفة أكبر من المفتاح المعطى
// فإن جميع العناصر النصف الأيمن من المصفوفة هي كذلك أكبر من
// العنصر المعطى لذا نبدأ البحث في النصف الأيسر من المصفوفة
high = mid - 1;
}
else if (midVal == key) {
// أضيفت هذه الحالة لغرض التوضيح فقط
// إن كانت القيمة في وسط المصفوفة مساوية للمفتاح المعطى
// فقد عرفنا حينئذٍ أن المفتاح المعطى موجود في المصفوفة
ans = true;
break;
}
}
return ans;
}
int main()
{
cout << contains(0, n-1, 3) << "\n";
cout << contains(0, n-1, 4);
}
موقع الظهور الأول للمفتاح المعطى
تعطي طريقة البحث هذه موقع الظهور الأول للمفتاح المعطى وهي مشابهة لعمل التابع std::lower_bond(…).
Input : 2 3 3 5 5 5 6 6
Function : first(3)
Returns : 1
Function : first(5)
Returns : 3
Function : first(4)
Returns : -1
يعرض المثال التالي طريقة تنفيذ عملية البحث هذه:
int first(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// إن كانت القيمة في وسط المصفوفة أقل من المفتاح المعطى
// فإن جميع العناصر في النطاق
// [low, mid]
// ستكون أصغر كذلك لذا سنبحث في النطاق
// [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// إن كانت القيمة في وسط المصفوفة أكبر من المفتاح المعطى
// فإن جميع العناصر في النطاق
// [mid + 1, high]
// ستكون أكبر كذلك لذا سنبحث في النطاق
// [low, mid -1]
high = mid - 1;
}
else if (midVal == key) {
// إن كانت القيمة في وسط المصفوفة مساوية للمفتاح المعطى
// فسنسجل آخر موقع عُثر عليه ثم نبحث عن المزيد من المواقع
// في الجانب الأيسر للقيمة الوسطى
// أي سنبحث في النطاق
// [low, mid - 1]
ans = mid;
high = mid - 1;
}
}
return ans;
}
int main()
{
cout << first(0, n - 1, 3) << "\n";
cout << first(0, n - 1, 4);
}
موقع الظهور الأخير للمفتاح المعطى
تعطي طريقة البحث هذه موقع الظهور الأخير للمفتاح المعطى.
Input : 2 3 3 5 5 5 6 6
Function : leastGreater(2)
Returns : 1
Function : leastGreater(5)
Returns : 6
يعرض المثال التالي طريقة تنفيذ عملية البحث هذه:
int last(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// إن كانت القيمة في وسط المصفوفة أقل من المفتاح المعطى
// فإن جميع العناصر في النطاق
// [low, mid]
// ستكون أصغر كذلك لذا سنبحث في النطاق
// [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// إن كانت القيمة في وسط المصفوفة أكبر من المفتاح المعطى
// فإن جميع العناصر في النطاق
// [mid + 1, high]
// ستكون أكبر كذلك لذا سنبحث في النطاق
// [low, mid -1]
high = mid - 1;
}
else if (midVal == key) {
// إن كانت القيمة في وسط المصفوفة مساوية للمفتاح المعطى
// فسنسجل آخر موقع عُثر عليه ثم نبحث عن المزيد من المواقع
// في الجانب الأيمن للقيمة الوسطى
// أي سنبحث في النطاق
// [mid + 1, high]
ans = mid;
low = mid + 1;
}
}
return ans;
}
int main()
{
cout << last(0, n - 1, 3) << "\n";
cout << last(0, n - 1, 4);
}
موقع أصغر عنصر يكون أكبر من المفتاح المعطى
وهي مشابهة لعمل التابع std::upper_bound(…).
Input : 2 3 3 5 5 5 6 6
Function : leastGreater(2)
Returns : 1
Function : leastGreater(5)
Returns : 6
يعرض المثال التالي طريقة تنفيذ عملية البحث هذه:
int leastgreater(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// إن كانت القيمة في وسط المصفوفة أقل من المفتاح المعطى، فإنّ جميع العناصر ضمن النطاق
// [low, mid - 1]
// ستكون أصغر من أو تساوي المفتاح المعطى
// عندها سنبحث في الجانب الأيمن لمنتصف للقيمة الوسطى
// لذا سنبحث في النطاق
// [mid + 1, high]
low = mid + 1;
}
else if (midVal > key) {
// إن كانت القيمة في وسط المصفوفة أكبر من المفتاح المعطى، فإنّ جميع العناصر ضمن النطاق
// [mid + 1, high]
// ستكون أكبر من أو تساوي المفتاح المعطى
// سنسجّل آخر موقع نعثر عليه، ثم
// نبحث في الجانب الأيسر لمنتصف للقيمة الوسطى
// لذا سنبحث في النطاق
// [low, mid -1]
ans = mid;
high = mid - 1;
}
else if (midVal == key) {
// إن كانت القيمة في وسط المصفوفة مساوية للمفتاح المعطى، فإنّ جميع العناصر في النطاق
// [low, mid]
// أصغر من أو تساوي المفتاح المعطى
// لذا سنبحث في النطاق
// [mid + 1, high]
low = mid + 1;
}
}
return ans;
}
int main()
{
cout << leastgreater(0, n - 1, 3) << "\n";
cout << leastgreater(0, n - 1, 4);
}
موقع أكبر عنصر يكون أصغر من المفتاح المعطى
Input : 2 3 3 5 5 5 6 6
Function : greatestLesser(2)
Returns : -1
Function : greatestLesser(5)
Returns : 2
تعرض الشيفرة التالية طريقة تنفيذ عملية البحث هذه:
int greatestlesser(int low, int high, int key)
{
int ans = -1;
while (low <= high) {
int mid = low + (high - low + 1) / 2;
int midVal = a[mid];
if (midVal < key) {
// إن كانت القيمة في وسط المصفوفة أقل من المفتاح المعطى، فإنّ جميع العناصر ضمن النطاق
// [low, mid - 1]
// ستكون أصغر من المفتاح المعطى
// عندها سنسجل آخر موقع نعثر عليه
// ثم نبحث في الجانب الأيمن لمنتصف للقيمة الوسطى
// لذا سنبحث في النطاق
// [mid + 1, high]
ans = mid;
low = mid + 1;
}
else if (midVal > key) {
// إن كانت القيمة في وسط المصفوفة أكبر من المفتاح المعطى، فإنّ جميع العناصر ضمن النطاق
// [mid + 1, high]
// ستكون أكبر من المفتاح المعطى
// عندها سنبحث في الجانب الأيسر لمنتصف للقيمة الوسطى
// لذا سنبحث في النطاق
// [low, mid -1]
high = mid - 1;
}
else if (midVal == key) {
// إن كانت القيمة في وسط المصفوفة مساوية للمفتاح المعطى، فإنّ جميع العناصر في النطاق
// [mid + 1, high]
// تكون أكبر من أو تساوي المفتاح المعطى
// عندها سنبحث في الجانب الأيسر من القيمة الوسطى
// لذا سنبحث في النطاق
// [low, mid - 1]
high = mid - 1;
}
}
return ans;
}
int main()
{
cout << greatestlesser(0, n - 1, 2) << "\n";
cout << greatestlesser(0, n - 1, 4);
}
انظر أيضًا
- البحث الخطي: البحث الخطّي Linear Search من أبسط خوارزميات البحث إذ أنّها تمر على عناصر المصفوفة واحدًا تلو الآخر بحثًا عن العنصر المطلوب.
- البحث القفزي: تتحقق خوارزمية البحث القفزي Jump Search (تعرف كذلك بخوارزمية البحث الكتلي Block Search) من عدد أقل من العناصر (مقارنة بالبحث الخطي) وذلك بالقفز عبر عناصر المصفوفة بخطوات ثابتة، بمعنى تجاوز بعض العناصر عوضًا عن البحث فيها كلّها.
- البحث الاستكمالي: تعدّ خوارزمية البحث الاستكمالي Interpolation Search تحسينًا على البحث الثنائي في بعض الحالات، إذ تكون القيم موزّعة بانتظام في مصفوفة مرتبة فتجري هذه الخوارزمية عملية التحقّق في مواقع مختلفة بالاعتماد على قيمة المفتاح المراد البحث عنه.
- البحث الأسّي: تقسّم خوارزمية البحث الأسّي Exponential Search المصفوفة التي يجري البحث فيها إلى مصفوفات فرعية يزداد عدد العناصر فيها ازديادًا أسّيًا (1, 2, 4, 8.... وهكذا إلى حين الوصول إلى مصفوفة جزئية يكون فيها العنصر الأخير أكبر من العنصر المطلوب.
مصادر
- الفصل السابع من OpenDSA Data Structures and Algorithms Modules Collection.
- صفحة Binary Search في توثيق الخوارزميات في موقع GeeksforGeeks.
- صفحة Variants of Binary Search في توثيق الخوارزميات في موقع GeeksforGeeks.