Binary Search Algorithm

Binary Search Algorithm

السلام عليكم و رحمة الله و بركاته ,,,,
رابط الموضوع الاول : Linear Search Algorithm
رابط الموضوع الثانى :Bubble Sort Algorithm

السلام عليكم و رحمة الله و بركاته ,,,,
كيف حالكم اخوتى ؟؟ ان شاء الله تكونوا بخـــــــــير
اليوم سنكمل الحلقة الاخيرة فى السلسلة التى اسميتها Sort & Search و هى تتكون من 3 حلقات :

• Linear Search Algorithm
• Bubble Sort Algorithm
• Binary Search Algorithm

فكرة هذه الخوارزمية فى انها تتبع السياسة الاستعمارية : Divide & Conquer بمعنى انه اولا يجب ان يتم ترتيب الخوارزمية فى ترتيب
تصاعدى او تنازلى ,ثم تقسيمها و البحث فى الجزؤ الذى يستوفى شروط البحث من ناحية الترتيب, لذا سنعتمد نحن اليوم على خوارزمية Bubble Sort لاستخدامها فى الترتيب .

ان خوارزمية Binary Search اكفأ كثيراً من خوارزمية البحث الخطي , و لكنها تحتاج الى ترتيب المصفوفة اولاً.

فكرة عمل الخوارزمية: (بعد عملية الترتيب باستخدام اى من خوارزميات الترتيب)
1- فى اول دورة يتم تحديد اذا كان العنصر الاوسط فى الخوارزمية يساوى قيمة مفتاح البحث .
2- لو كان ذلك صحيح , فإن الخوارزمية ينتهى عملها و ترجع قيمة العنصر الاوسط.
3- يتم تحديد اذا كان مفتاح البحث اصغر ام اكبر من العنصر الاوسط لمعرفى اى نصف من المصفوفة سيتم البحث فيه.
4- اذا كان اكبر من العنصر الاوسط , يتم البحث فى القسم الثانى و العكس صحيح بالنسبة للقسم الاول.
5- يتم تقسيم القسم المحدد البحث فيه , و يتم تحديد عنصره الاوسط مرة اخرى.
6- حلقة لإعادة كل ما سبق , حتى يتم الوصول الى مفتاح البحث (يتم الوصول اليه اذا كان العنصر لأحد الانصاف فى المصفوفة بعد عملية التقسيم)
========================

مثال مبسط :
عندنا مصفوفة تحتوى على 7 عناصر.
كالتالى (مرتبين ترتيب تصاعدى): 3 - 4 - 6 - 9 - 10 - 13 - 19
نحن نريد البحث عن العنصر 4 .
تحديد العنصر الاوسط : 9
المطلوب البحث عنه : 4
اصغر ام اكبر : اصغر
البحث فى القسم الاول.
-------------
تحديد العنصر الوسط فى القسم الاول : 4
اصغر ام اكبر : يساوى
الدالة رجع ترتيبه (1) باعتبار index = 0
===============================
اكواد الخوارزمية :
==============
كود الدالة swap

    //swap function
    void swap(int& x, int& y) //function used to swap values of two variables
    {
         int temp;
         temp = x;
         x = y;
        y = temp;
    }

============================
كود الدالة bubblesort

//bubblesort function
void bubblesort(int a[], const int SIZE)
{
    for (int pass=1; pass < SIZE; pass++) //loop to specify number of passes
    {
        for (int j=0; j < SIZE-1; j++) //shorter loop to check elements of array
        {
            if (a[j] > a[j+1]) //if element > following element then
                swap(a[j],a[j+1]); //swap them
        }
    }
}

=========================
كود الدالة binarysearch

//binarysearch function
int binarysearch(int a[], const int SIZE, int key)
{
    int low = 0; //lowest element in array
    int high = SIZE - 1; //last element in array
    int midpos; //variable to carry middle element
    while (low <= high) //WHILE loop to check data in array
    {
        midpos = (low + high)/2; //calculate middle element position
        if (a[midpos] == key) //IF statement to check if key == middle element
        {
            return midpos; //return position of middle element
        }
        if (a[midpos] < key) //IF middle element < key
        {
            low = midpos + 1; //continue search in a[midpos+1 ....high]
        }
        else //IF middle element > key
        {
            high = midpos - 1; //continue search in a[low....midpos-1]
        }
    }
    return -1;
}

اعتقد ان هذه الدالة هى التى تحتاج شرح لأن الدوال المذكورة شرحت فى الحلقتين السابقتين
السطر 3: تعريف بداية الدالة
functio paramters: array a[] ,size of array SIZE, search key
السطر 5: اصغر عنصر فى المصفوفة
السطر 6: العنصر قبل الاخير فى المصفوفة
السطر 7: العنصر الاوسط فى المصفوفة
السطر 9: بداية حلقة دوارة while loop للبحث فى جميع عناصر المصفوفة
السطر11: لتحديد index الخاص بالعنصر الاوسط
السطر13: جملة IF للتأكد ان كانت قيمة العنصر الاوسط تساوى مفتاح البحث
السطر 18: اذا كانت قيمة العنصر الاوسط اصغر من قيمة مفتاح البحث
السطر 20: القيمة السفلى low تساوى عنوان العنصر الاوسط + 1 (لأن البحث سوف يكون من a[midpos+1 ....high]
السطر 25: اذا كانت قيمة العنصر الاوسط اكبر من قيمة مفتاح البحث ... قيمة high تساوى عنوان العنصر الاوسط -1 لأن البحث سيكون فى a[low....midpos-1]
السطر 28: اذا لم يوافق مفتاح البحث اى من الشروط السابقة ... ترجع حلقة while قيمة -1


=========================
كود الدالة المفضلة :) main

#include<iostream>using namespace std;void bubblesort(int[],const int); //function prototypevoid swap(int&, int&); //function prototypeint binarysearch(int[],const int, int); //function prototypeint main(){    const int SIZE = 100; //constant for sizing the array    int a[SIZE]; //declaring array    for (int i=0; i < SIZE; i+=2) //Loops used to fill array with non-arranged data    {        a=i*3;    }    for (int i=1; i < SIZE; i+=2)    {        a=i+2;    }    bubblesort(a,SIZE); //applying bubblesort function    int key;    cout << "Enter key: ";    cin >> key; //aquiring data from user    int element = binarysearch(a,SIZE,key); //declaring variable to carry data    if (element != -1) //if data returned != -1 //returned from binarysearch functio        n    {        cout << "Value " << key << " is found in element no. : " << element << endl; //displayi        ng result    }    else    {        cout << "Value not found" << endl;    }    system("pause");    return 0;}

=cpp>=cpp>ما يحتاج لقليل من الشرح ...
السطر 13 -< 20: حلقتى for loop ليملأوا المصفوفة ببيانات غير مرتبة
================================================
الى هنا انتهى الشرح ,,,,
ارجو ان اكون وفقت فى توضيح هذه الخوارزمية بشرحى البدائى جدا هذا .....

ملحوظة : كود البرنامج كاملا فى المرفقات=cpp>=cpp>=cpp>

binary_search.rar