عيون العرب - ملتقى العالم العربي - Binary Search Algorithm نادر ^^^

https://4.top4top.net/p_1235dil6k1.jpg

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 functionvoid 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 functionint 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]=i*3;    }    for (int i=1; i < SIZE; i+=2)    {        a[i]=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>=cpp>ما يحتاج لقليل من الشرح ...
السطر 13 -< 20: حلقتى for loop ليملأوا المصفوفة ببيانات غير مرتبة
================================================
الى هنا انتهى الشرح ,,,,
ارجو ان اكون وفقت فى توضيح هذه الخوارزمية بشرحى البدائى جدا هذا .....

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

Binary-Search.rar