commando161

Binary Search Algorithm

5 ردود في هذا الموضوع

Binary Search Algorithm



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

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


فكرة هذه الخوارزمية فى انها تتبع السياسة الاستعمارية : 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

تم تعديل بواسطه مصطفى 36a2
الترتيب الخطي -> البحث الخطي , إنقاذ الأكواد
1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

جميل جداً و اضافة الى هذا يعتبر الBinary Search من الخوارزميات السريعة فيمكنه الوصول للنتيجة في( O(log n

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

اشكرك على شرحك الواضح

كنت خايفه من search ومن شرحك سهل علي كل شي 

يعطيك العافيه اتمنى تواصل شروحات

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

غزيزي الكاتب ,

هناك خطا كبير في عملية برمجتك لل Binary Tree واساسيات بنائها في Data structure

عزيزي  Binary Tree كما معروف عنها وحسب طرق البحث الثلاثة الخاصة بها كما هي مبينة  هنا من جامعة ستانفورد

http://cslibrary.stanford.edu/110/BinaryTrees.html

 

فانت لم  تتبع الخورازمية  في عملك بمعنى انت تحل بطريقة صحيحة برمجيا لكن خطا من باب   Data structure اي انك لم تتبع الخورزمية في حلك وخاصة في البحث ( اي انك ترتب عناصر مصفوفة بقليل من التعقيد )

وكذالك الهيكلية  Binary Tree فهمي ليست مصفوفة بعدد محدد من العناصر هي  ثلاث مؤشرات لكل عنصر(البيانات , لمؤشر اليمن, المؤشر لأيسر) لان قد تكون السلسلة المدخلة لترتيبها غير محددة العناصر  وهو مامعروف عن اي سلسلة لترتبها انت لاتعرفها وليس 100 كما انت مفترض في حلك . وبالاخص هوا يحاول بهذه الخارزمية يريك عمل المترجم في ترتيب البيانات

 

لذالك اتمنى منك العمل على الخوارزمية بشكل صحيح في شرحك حتى يكون واضح للفهم بين الشرح والكود

تم تعديل بواسطه حسين احمد طالب
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

أخي حسين هو لم يتحدث عن binary tree

وإنما خوارزمية البحث الثنائي

ويمكن تنفيذها في المصفوفات بإستبعاد النصف كل مرة

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .