ممكن شرح لل البحث الثنآئي ( Binary )

وعليكم السلام ورحمة الله وبركاته ,

/index.php?showtopic=169156

بسم الله ،، يجب أولا ترتيب المصفوفة تنازليا او تصاعديا باستخدام اي من خوارزميات ال sort و أفضل ال heap sort لأن تكلفتها قليلة

ثانيا ،، تحديد اول عنصر في المصفوفة و أخر عنصر في المصفوفة و العنصر الموجود في منتصف المصفوفة

ولنسمي العنصر الاول i

والاخير j

والذي في نصف المصفوفة k

بعد ذلك نقارن العنصر الذي نريد البحث عنه مع العنصر k اذا كان يساويه فلقد وصلنا الى مبتغانا ،، اما اذا كان العدد المطلوب البحث عنه ولنسميه x اكبر من k فيجب ان يكون في الجانب الايمين (على يمين k ) أما اذا كان أصغر فيجب أن يكون على يسار K

وهنا أيضا لديك خياران (نظرا لوجود عدة نسخ او طرق لتنفيذ البحث الثنائي )

على سبيل المثال لنفرض أن x أكبر من k اذن هو موجود على يمينه

لذا باستطاعتك مقارنة x مع كل الاعداد على يمين k

وهذه طريقة رديئة في حال كان هناك الكثير من الاعداد على يمين k

او ان تقومي باعتبار كل الاعداد على يمين k هي مصفوفة ثانية ( مصفوفة جزئية ) وتقومي بتعيين أول عنصر فيها واخر عنصر والعنصر الذي في المنتصف واعادة المقارنة مع العنصر الذي في المنتصف مرة أخرى

طبعن يمكنك برمجتها من خلال ال Recursion

ولتسهيل الامر سأعطيك مثال

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

على فرض أن هذه هي مصفوفتنا بعدما قمنا بترتيبها اذن

i=0

j=19

k=11

نريد البحث عن 13

اذن ال13 اكبر من k لذلك هي على يمينها لذلك نقوم باعادة تعيين ال i , j , k بحيث

i=11

j=19

k=15

بنحث مرة أخرى ال 13 اقل من ال 15 لذلك نقوم باعادة تعيين كل من i.k.j

i=11

j=15

k=13

ال 13 = K

اذن وصلنا

انتهى

مع مراعاة أن k = array size /2+1

المهم أن تستخدمي نفس المقدار لحساب k كل مرة

ان شاء الله تكون انفهمت

يعطيكم الف عافيــه بس انا عارف طريقه البحث الثنائي بس المشكله الاكواد اعرف وش تسوي بس قواعدها احسها صعبه الفهم

يعني مثلا ياليت احد يشرح لي بالتفصيل لـ هالكود هذا .. !!!!

int BinarySearch(int A[], int Key, int left, int right) {
      while (left <= right) {
            int middle = (left + right) / 2;
            if (A[middle] == Key)  return middle;
            else if (A[middle] > Key) right = middle - 1;
            else  left = middle + 1;
      }
      return -1;
}

وشرح هالكود بالارقام .. لانه احس ان هذا اسرع طريقه بالبحث اسرع من السابق ذكره

#include <iostream>
using namespace std;
int b_search(int[],int,int );
int arr[]={1,2,3,4,5,6,7,8,9,10,11};
int main()
{
	int s;
    cout<<" Enter the the number  : ";
	cin>>s;
	cout<<s<<" is found in order "<<b_search(arr,14,s)<<endl;
	return 0;
}
int b_search(int arr[],int size,int key)
{
	int i=0,j=size,k=(i+j)/2;
	while (1)
	{
		if(arr[k]==key) 
			return k;
		else
		{
			if(key<arr[k])
			{
				j=k;
				k=(i+j)/2;
			}
			else if(key>arr[k])
			{
				i=k;
				k=(i+j)/2;
			}
		}
	}
	return -1;
}

ياليت ياخوي تشرح لي بالتفصيل مع مثال بارقام مثل ماتفضلت

والله يقويكم

السلام عليكم ورحمة الله وبركاته . ,

int BinarySearch(int A[], int Key, int left, int right) {
     while ( left <= right) {
            int middle = (left + right) / 2;
            if (A[middle] == Key)  return middle;
            else if (A[middle] > Key) right = middle - 1;
            else  left = middle + 1;
      }
      return -1;
}

بشرح لك هالدالة بمثال ..

لو كانت الـ Array كالتالي ..

A[]={1,2,3,4,5,6,7,8,9,10} ;

ستكون الـ left , right

 left = 0 ; right=9

و كان الـ key يساوي ..

key=7 ;

while ( left <= right)

بيشك على أول عنصر لا زال أقل أو يسآوي آخر عنصر ..

لأن لو كآن غير كذا , معناته أن أنتهيت من البحث في المصفوفة ولم أجد العنصر و بيرجع بـ -1 ,

int middle = (left + right) / 2;

بيقسم المصفوفة إلى قسمين .. بيصير قيمة الـ

middle  = (0+9)/2 = 4

if (A[middle] == Key)  return middle;

بعد ما قسمنآ المصفوفة إلى قسمين , بنقارن قيمة العنصر الأوسط مع مفتاح البحث

لو طلع متساوي

بيرجع قيمة الـ index للـ العنصر الأوسط اللي هو مفتاح البحث ..

في مثالنا ..

A[4]=5

الـ 5 لا تساوي 7 , يعني يا أصغر أو أكبر ..

إذا ما تحقق الشرط ,

else if (A[middle] > Key) right = middle - 1;

الحين المقارنة بتتم على الـ key , و العنصر [A[middle

إذا كان [A[middle أكبر من الـ key ..

أجعل قيمة الـ

 right = 4-1 = 3

أما إذا كان الـ [A[middle أصغر من الـ key ..

else  left = middle + 1;

في مثالنا .. 5 أصغر من الـ 7

يعني بتصير قيمة

left = 4+1 = 5

كأننا تخلصنا من الجزء الأول من المصفوفة من العنوآن 0 إلى العنوآن 4 ..

و صارت قيم الـ left = 5 , right = 9 .. ,

و هكذا إلى أن يجد العنصر 7 ..

بإختصار , الدالة تقوم على تقسيم المصفوفة إلى قسمين , و العنصر الأوسط هو اللي بتقارنه مع مفتاح البحث , إذا وجدته رجع بـ index

أما إذا كان العنصر الأوسط أكبر من مفتاح البحث ( يعني المفتاح يوجد في القسم الأول من المصفوفة ) .. ف أننا نتخلص من القسم الثاني من المصفوفة و نبحث في القسم الأول . ,

و إذا كان أصغر ف نتخلص من القسم الأول و نبحث في القسم الثاني ..

وآضح الأن ؟

حاول ترسم وأنت تتبع الخوآرزمية علشان توضح لك أكثر ..

بالتوفيق يآرب :happy:..

ربي يعطيك الف عافيــه .. مفهومـه ..

ماقصـرت يالغالي

طيب اخوي انا كتبت كــود من عنــدي .. من فهمي لـ شرحك ..

بس المشكله يكرر النتيجه الى الابــد .. ابي حـل لهالشغله ..

#include<iostream.h>
void main()
{
	int a[]= {1,2,3,4,5,6,7,8};
	int b,e,z=0,i,s;
	b=0;
	e=7;
	cin>>s;
	z=(b+e)/2;
	for(int n=0;n<=z;n++)
	{
		if(a[z]==s)
		{
			cout<<z<<"-"<<a[z];
		n==1000;
		}
		else if(a[z]<s)
		{
			b=z;

			z=(b+e)/2;

		}
		else if(a[z]>s)
		{
			e=z;
			z=(b+e)/2;

		}
	}
}

عطني حـل لـ هالكود ووين مكان الخطاء ..

آلسلام عليكم ورحمة الله وبركاته .. ,

حلك صحيح لكن فيه أخطاء بسيطة ..

أولاً :

z=(b+e)/2;

و ضعتهآ خارج الـ loop و هذآ خطأ , لأن كل شغلك داخل الـ loop يعتمد على الـ z في كل رآوند رآح تتغير قيم الـ e , b وبالتالي لازم تتغير قيمة الـ z ,

ثآنياً :

for(int n=0;n<=z;n++)

الـ for تستخدمهآ إذا كنت تعرف إلى متى بيوقف .. , لكن في البحث بتشوف هل البداية لا زالت أقل أو تساوي النهآية ..

يعني تستخدم while ,

أخيراً

n==1000;

لآداعي من وجودها , إذا أردت الخروج من الـ loop , أكتب break مثلاً .. ,

الكود بعد التصحيح :

#include<iostream.h>
#include<conio.h>
void main()
{
        int a[]= {1,2,3,4,5,6,7,8};
        int b,e,z=0,i,s;
        b=0;
        e=7;
        cout<<"Enter key: "<<endl;
        cin>>s;
        while(b<=e)
        {
                z=(b+e)/2;
                if(a[z]==s)
                {
                        cout<<z<<"-"<<a[z];
                        break;
                }

                else if(a[z]<s)
                {
                        b=z;
                        z=(b+e)/2;
                }

                else
                {
                        e=z;
                        z=(b+e)/2;
                }
        }
getch();
}

موفق يآرب :)

..

ربي يعطيك الف عافيه .. انا عارف الـ بريك بس ممنوع اني احطهـا بالجامعه بسبب سهولتها

وجزاك الله خير