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

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

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

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

repeat:
If ID <= Array[k] then j=k-1
If ID >= Array[k] then i=k+1
until i>=j
If i-1>j then we found the ID in the array
else the ID is not found

لا تقلق، سيساعدك الفلاش التالي على فهم التكنيك بصورة مرئية إن شاء الله بفرض أن مصفوفتنا التي نبحث فيها هي التالية (لاتنسى أنها مرتبة ترتيباً أبجدياً):

word[]={"begin", "const", "do", "end", "if", "odd", "program", "read", "then", "var", "while", "write"}



والسؤال الآن: كيف نكتب code يمثل هذا الخوارزم بالسي؟!
وللإجابة على هذا السؤال ستصادفنا تساؤلات أخرى:

كيف نرتب المصفوفة أبجدياً؟!

كيف نبحث في مصفوفة جميع عناصرها رموز(حروف) أو سلاسل رمزية(حرفية) ونقارن الترتيب الأبجدي؟!


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

strcmp (char *str1, char *str2)

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

القيمة (صفر) إذا كانت str1= str2.

قيمة سالبة إذا كانت str1< str2.

قيمة موجبة إذا كانت str1> str2.

وبعد أن اجبنا على جميع الأسئلة، لنرى سوياً الـcode الذي يمثل خوارزم الـbinary search الثاني بلغة السي:

#include "STRING.H"
#include "STDIO.H"
#define max_size 12


//-------------------------------
int binary_search (ID)
char *ID;
{
char *word[]={"begin", "const", "do", "end", "if", "odd", "program", "read", "then", "var", "while", "write"};

int i=0, j=max_size-1, s, k;
while(i<=j)
{
k=(i+j)/2;
s=strcmp(ID, word[k]);
if (s<=0) j=k-1;
if (s>=0) i=k+1;
}
if((i-1)>j){
printf("\nwe found the key (%s) at element %i", word[k], k+1);
return k;
}
return -1;
}
//--------------------------------
void main()
{
int result;
char *ID;
printf("\n\nPlz. Enter the ID to begin search\nID=");
scanf("%s",ID);
result = binary_search(ID);
if (result==-1){
printf("\nthe key(%s) is not found",ID); }
getch();
}

وبذلك نكون قد انتهينا من الحديث عن الـBinary Search أرجو من الله العلي القدير أن يكون كل شئ واضح ومفهوم.
وفق الله الجميع لما يحب ويرضى..

منقول للأهمية

أختكم
أم حيدر علي