Home برمجة جافا خوارزمية البحث الثنائى Binary search
خوارزمية البحث الثنائى Binary search

خوارزمية البحث الثنائى Binary search

43
0

بسم الله الرحمن الرحيم

والصلاة والسلام على أشرف المرسلين سيدنا محمد صلى الله علية وسلم

افترض انك تبحث عن شخص فى دليل التليفون وكان اسمة يبدأ بحرف الكاف (بالطريقة التقليدية) فأنت تبدأ بفتح الدليل وتبحث من الصفحة الاولى وتقلب الصفحات الى أن تصل للصحفة التى بها حرف الكاف . لكن كان من الافضل ان تبدأ من منتصف الدليل لانك تعلم أن حرف الكاف ليس من الحروف الاولى فى الترتيب الابجدى

افترض انك مسجل فى Facebook  عندما تقوم بعمل دخول sign in  فأن Facebook  يجب ان يتأكد ان اسم المستخدم موجود لدية فى الdatabase  اى يبحث عنة ومن الافضل ان يبدأ البحث فى الdatabase  من نقطة فى الوسط

هذة التطبيقات وغيرها  كثير عبارة عن مشاكل بحثsearch problem   تستخدم او تحتاج لاستخدام خوارزمية binary search  لحلها.

Binary search  هى عبارة عن خوارزمية المدخل لها عبارة عن قائمة بها عناصر مرتبة والمخرج منها عبارة عن موقع العنصر الذى تبحث عنة

مثال:

لكى نفهم كيف تتم العمليات فى binary search  المثال عبارة عن لعبة التخمين وفيها  اعطيك قائمة مرتبة  بها الارقام من 1 الى 100

وانت عليك ان تخمن الرقم الذى اخترتة فى اقل عدد من التخمينات وكل مرة تقوم بتخمين رقم سوف ارشدك بأننى اقول لك الرقم كبير جدا too high او صغير جدا too low او صحيح  correct

لنبدأ :

كما بالصورة الرقم الصحيح هو 7 وقام اللاعب بتخمين رقم واحد فكانت الاجابة too low

ثم قام اللاعب بتخمين الرقم 2 وكانت الاجابة too low فقام بالغاؤة الى ان وصل اللاعب للرقم 7 وهو الرقم الصحيح , نلاحظ فى هذة الطريقة انك بدأت من البداية للقائمة بالرقم واحد وعندما كان خطأ خذفتة وقلت الرقم الذى يلية وهكذا الى ان تصل للرقم الصحيح .

لكن هناك طريقة افضل فى البحث  هى :

ان تبدأ بالرقم فى الوسط middle  وليكن 50 فتكون الاجابة too low  لذلك انت تقوم بالغاء الارقام من 1 الى 50 دفعة واحدة

ثم تبدأ بتخمين رقم جديد وليكن 75  فتكون الاجابة too high

مرة اخرى تقم بالغاء الارقام من 75 الى 100 وتكون الارقام المرجح انها صحيحة بين 51 الى 74 وهكذا الى ان تصل للرقم الصحيح

هذة هى خوارزمية البحث الثنائى لو اردنا حساب كم رقم ممكن ان نحذفة فى كل خطوة  iteration

فمهما كان الرقم الذى افكر فية فيمكنك ان تستنتجة فى 7 خطوات iteration  فقط لانك فى كل مرة تخمن فيها رقم  سوف تقوم بالغاء نصف الارقام .

للتوضيح اكثر تخيل اننا نبحث عن كلمة فى قاموس والقاموس بة 240,000 كلمة  فكم عدد الخطوات سوف تأخذ الخوارزمية العادية وخوارزمية البحث الثنائى لايجادها

فى الخوارزمية العادية فى اسوء الحالات لو كانت الكلمة اخر كلمة فى القاموس فسوف تأخذ 240,000 خطوة لايجاد الكلمة اما خوارزمية البحث الثنائى ففى كل خطوة سوف تقوم بتقسيم الكلمات الى نصفين وتلغى احدهما الى ان تصل الى كلمة واحدة فقط

اذا سوف تأخذ 18 خطوة فقط اكيد طبعا فرق كبير بين عدد الخطوات فى الخوارزميتين

بصورة عامة فأن خوارزمية البحث الثنائى  اذا كان لدى قائمة مكونة من n  عنصر فهى تأخذ عدد من الخطوات بمقدار  log2 n لايجاد اى عنصر فى قائمة

ملحوظة :

عند استخدام خوارزمية البحث الثنائى يجب ان تكون العناصر فى القائمة مرتبة sorted list

Running time

عند التحدث عن اى خوارزمية يجب ان نتحدث عن كفائتها من حيث إما :

  •  الوقت running time
  • أو المساحة فى الذاكرة space

بالنسبة لخوارزمية البحث الثنائى كم هو الوقت الذى نحفظة عند استخدامها ؟

لو نظرنا الى الخوارزمية العادية نجد اننا نختبر كل عنصرمرة تلو الاخرى اى اذا لدينا قائمة بها 100 عنصر فسوف نخمن 100 مرة واذا لدينا قائمة بها 4 بليون عنصر سوف نخمن 4 بليون مرة اى عدد التخمينات يكون مساوى لحجم القائمة ونطلق على ذلك ان الخوارزمية تعمل فى  linear time او O(n)
فى خوارزمية البحث الثنائى الامر مختلف اذا لدينا قائمة بها 100 عنصر سوف يكون عدد التخمينات 7 مرات واذا لدينا قائمة بها 4 بليون عنصر سوف يكون عدد التخمينات 32 مرة اى ان الخوارزمية تعمل فى log time اى  O(log(n))    كما موضح بالشكل

الكود بالبايثون:

اذا اردنا كتابة الكود للبحث عن رقم ما بالقائمة -فهذا الكود يبحث عن رقم 3 بالقائمة

[1, 3, 5, 7, 9]

الكود بالجافا

 

رجاء:لا تنسونى من الدعاء عن ظهر غيب

رَبِّ إِنِّي لِمَا أَنزَلْتَ إِلَيَّ مِنْ خَيْرٍ فَقِيرٌ

الحمد الله رب العالمين والصلاة والسلام على أشرف المرسلين سيدنا محمد صلى الله علية وسلم وعلى اله وصحبة وسلم -اللهم دومها نعمة وأحفظها من الزوال -أمين

(43)

مشاركة