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

البحث الثنائي (1) Binary Search



بسم الله الرحمن الرحيم

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

طريقة البحث الثنائي Binary Search:

يصادف المبرمج دوماً العمل مع كمية بيانات كبيرة مخزنة في مصفوفة، ومن الضروري أن يستخدم تكنيك معين يحدد له ما إذا كان العنصر الذي يبحث عنه key ينتمي إلى هذه المصفوفة أم لا! هذا التكنيك يطلق عليه "البحث" وله عدة أنواع، من أشهرها وأكثرها فاعلية طريقة البحث الثنائي.

ولكي نطبق أحد خوارزميات الـBinary Search على مصفوفة ما نتبع الخطوات البسيطة التالية:

الخطوة الأولى والأهم والتي لا يمكن تطبيق الـBinary Search لولاها هي:
ترتيب المصفوفة تصاعدياً أو تنازلياً أو أبجدياً على حسب نوع البيانات المخزنة فيها!
تحديد أول عنصر في المصفوفة ولنسمه i، وآخر عنصر فيها ولنسمه مثلاً j.
تحديد العنصر الذي يقع في منتصف هذه المصفوفة ولنسمه k.

بعد ذلك يمكننا تطبيق تكنيك البحث الثنائي على مصفوفتنا، وهناك عدة خوارزميات للبحث الثنائي، سأشرح أحدها في هذا الدرس على مصفوفة ذات بيانات رقمية، وسأشرح خوارزم آخر على مصفوفة ذات بيانات حرفية أو رمزية في الدرس التالي إن شاء الله، وبذلك نكون استوفينا شرح الخوارزميات وأيضاً المصفوفات المختلفة البيانات.

خوارزم البحث الثنائي الأول First Binary Search Algorithm:

تقوم فكرة البحث الثنائي على تقسيم المصفوفة إلى نصفين واستبعاد النصف الذي لا ينتمي إليه المفتاح key الذي نبحث عنه، كيف ذلك؟
عن طريق تحديد العنصر الذي يقع في منتصف هذه المصفوفة، ثم نقارن هذا العنصر مع المفتاح الذي نبحث عنه كالتالي (تذكر أن مصفوفتنا مرتبة تصاعدياً أو تنازلياً):

إذا كان يساويه نكون قد وجدنا العنصر الذي نبحث عنه.

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

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

بعد ذلك: نعتبر النصف الذي حددنا لأنفسنا البحث فيه مصفوفة قائمة بحد ذاتها، نحدد فيها الـi, j, & k (أي نقوم بتقسيمها إلى قسمين) ونطبق نفس الخطوات من 1 إلى 3 فيها، ثم نقارن المفتاح مع العنصر الأوسط الجديد، بنفس الترتيب الذي ذكر في الخطوات 1 إلى3 السابقة.

سيساعدك المثال التالي على فهم الطريقة إن شاء الله:
-نفرض أننا نبحث عن عناصر مختلفة في هذه المصفوفة:

Array[]={0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28}

-تابع في هذا الفلاش التسلسل في البحث عن عناصر مختلفة:

والسؤال الآن: كيف نكتب code يمثل هذا الخوارزم بالسي أو الجافا؟!
وللإجابة على هذا السؤال سيصادفنا تساؤل آخر: كيف نرتب المصفوفة تصاعدياً او تنازلياً؟!
والإجابة:
لترتيب المصفوفة فهناك عدة خوارزميات للترتيب منها مثلاً: (Bubble sort, sorting by Selection, sorting by Insertion, Shell sort, & Quick sort).
ولا مجال لذكرها الآن، حيث سنعتمد في الـcode على ترتيبنا نحن للمصفوفة بشكل صحيح.

والآن، لنستعرض معاً code يطبق تكنيك binary search على مصفوفة ذات عناصر رقمية بلغة السي:



#include "STRING.h"
#include "STDIO.h"
#define max_size 15

//-------------------------------
int binary_search (key)
int key;
{
int NumArray[]={0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28};

int i=0, j=max_size-1, k=(i+j)/2;
while(i
if (key = NumArray[k]){
printf("nwe found the key (%i) ", key);
return k;
}
else{
if (key < NumArray[k]){
j=k;
k=(i+j)/2;
}
if (key > NumArray[k]){
i=k;
k=(i+j)/2;
}
}
}
return -1;
}
//--------------------------------
void main()
{
int result;
int key;
printf("nnPlz. Enter the Key to begin searchnKey=");
scanf("%i",key);
result = binary_search(key);
if (result==-1){
printf("nthe key(%i) is not found",key); }
getch();
}

أرجو أن يكون هذا المثال البسيط جداً واضحاً.

عدد مرات البحث في أي مصفوفة عن عنصر محدد باستخدام الـBinary Search:

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

ففي مثالنا: استخدمنا مصفوفة من 15 عنصر، نلاحظ ان العدد الذي يزيد على عدد عناصر المصفوفة بواحد، أي العدد 16 ينتج من القوة الرابعة لرقم2 (2^4=16) وذلك يعني اننا نحتاج على الأكثر لأربع مرات مقارنة في الـBinary Search حتى نجد العنصر الذي نبحث عنه! فمن الممكن أن نجده من أول مرة في المقارنة، ومن الممكن أن نجده في ثاني مرة، أو ثالث مرة أو رابع مرة.. أو أن يكون غير موجود في المصفوفة!

وفي مثال آخر: لو بحثنا في مصفوفة تحوي 1024 عنصر، سنحتاج إلى 10 مرات للمقارنة كحد أقصى، ونعرف ذلك بتكرار قسمة عدد العناصر على رقم 2 إلى أن نصل إلى العدد واحد في خارج القسمة (وسبب ذلك هو أننا بعد كل مقارنة نقوم بإلغاء نصف عناصر المصفوفة من الاعتبار)، فبتكرار قسمة 1024 على رقم 2 نحصل على القيم التالية على الترتيب: 512، 256، 128، 64، 32، 16، 8، 4، 2، ورقم 1. نلاحظ أن العدد 1024 (2^10) قسم على رقم 2 عشر مرات حتى حصلنا على العدد 1.
نستنتج من ذلك، أن القسمة على اثنين تقابل مرة واحدة من المقارنة في الـBinary Search Algorithm. فمصفوفة بـ 1048576 (2^20) عنصر تستلزم على الأكثر 20 مرة من المقارنة حتى نجد العنصر الذي نبحث عنه، ومصفوفة تحوي بليون عنصر، تستلزم على الأكثر إلى 30 مرة من المقارنة حتى نجد العنصر المطلوب فيها!

ترى، كم يوفر لنا هذا التكنيك من الوقت في البحث؟.. فقط 30 مرة من البحث بين بليون عنصر لنجد ضالتنا!!.. إنه تكنيك عبقري فعلاً

تابعنا في الدرس الثاني كي تتعرف على الخوارزم الثاني للـBinary Search