عيون العرب - ملتقى العالم العربي

العودة   عيون العرب - ملتقى العالم العربي > عيــون الأقسام العلمية > علوم و طبيعة > علم البرمجيات

إضافة رد
 
LinkBack أدوات الموضوع انواع عرض الموضوع
  #1  
قديم 05-20-2019, 01:19 PM
 
Binary Search 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 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
__________________
رد مع اقتباس
إضافة رد

مواقع النشر (المفضلة)

أدوات الموضوع
انواع عرض الموضوع

تعليمات المشاركة
لا تستطيع إضافة مواضيع جديدة
لا تستطيع الرد على المواضيع
لا تستطيع إرفاق ملفات
لا تستطيع تعديل مشاركاتك

BB code is متاحة
كود [IMG] متاحة
كود HTML معطلة
Trackbacks are متاحة
Pingbacks are متاحة
Refbacks are متاحة


المواضيع المتشابهه
الموضوع كاتب الموضوع المنتدى مشاركات آخر مشاركة
Incoming search terms for the article hjfh58hfdg أرشيف المواضيع الغير مكتمله او المكرره او المنقوله و المخالفه 0 04-17-2011 06:55 AM
ice hockey jersey Search Engine Marketing, Search qlulljca85 أرشيف المواضيع الغير مكتمله او المكرره او المنقوله و المخالفه 0 03-03-2011 10:08 AM


الساعة الآن 11:21 PM.


Powered by vBulletin®
Copyright ©2000 - 2019, vBulletin Solutions, Inc.

شات الشلة
Powered by: vBulletin Copyright ©2000 - 2006, Jelsoft Enterprises Ltd.
جميع الحقوق محفوظة لعيون العرب
2003 - 2011