الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

البحث الثنائي Binary Search

بدأه aohammed في 27 نوفمبر 2010 · 7 رد · 2,929 مشاهدة · في الرياضيات والخوارزميات
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

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

تعريف :

عندما يُطلب من أحدنا البحث عن شيء فإنه يبدأ من الصفر إلى النهاية كي يجده و يعتقد أنه لن يستطيع توفير أي وقت في البحث و ذلك لأنه في حال غض النظر عن أي مكان فإنه من الممكن أن يكون هنالك الشيء الذي تبحث عنه .

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

و عندما يصل العداد إلى n فهذا يعني أنه لم يعثر على المفتاح

 For(i=0 ; i<n; i++)
{
if(key==a[n])
return n;
}

و لكن أحيانا ً تكون اللائحة ضخمة جدا ًو يصبح من الصعب البحث في كل حجرة , لذا فمن الأولى أن نطبق البحث الثنائي

البقية في المرفق ,, أتمنى في حال أي إضافة أو خطأ التنبيه عليه

البحث الثنائي.pdf

2
#2

يمكنك توليد أرقام عشوائية عن طريق حركة الماوس على الشاشة وذلك بأخذ إحداثيات الماوس و ضرب x بـ y و لتكن تلك نتيجة البذرة seed, ما رأيك بهذه الطريقة !؟

1 −2
#3
أحمد المتألق كتب:

يمكنك توليد أرقام عشوائية عن طريق حركة الماوس على الشاشة وذلك بأخذ إحداثيات الماوس و ضرب x بـ y و لتكن تلك نتيجة البذرة seed, ما رأيك بهذه الطريقة !؟

ما هی فائدة هذه البذرة فی البحث؟ هل من الممکن التوضیح؟

تم تعديل هذه المشاركة بواسطة u77431 في 28 نوفمبر 2010 في 16:04

1 −1
#4

جميل جدا بارك الله فيك

291964_260506123967115_206850989332629_1001538_45132_n.jpg

اللهم إني أعوذ بك من علم لا ينفع ، ومن قلب لا يخشع ، ومن نفس لا تشبع ، ومن دعوة لا يستجاب لها

#5

* الترتيب التصاعدي او التنازلي غير لازم. لذا اقترح تشيل النقطة رقم 1

* شرحك قد يؤدي إلى سوء فهم. لانك عندما تقسم الsearch space إلى اثنين، فأنت تذهب في احدى الاتجاهات . بينما شرحك يذهب في الاجتاهين.

* كذلك الbinary search ليس فقط بهذه الآلية... يعني انت هنا تقسم جميع العناصر إلى اثنين في هذه الحالة.. لكن ليس دائما تقسم الى قسمين.

كل مافي الأمر ان binary search يسأل سؤال جوابه binary بنعم او ﻻ.. فقط.... وانت ممكن تبدع فيها

سواء تقسمه إلى قسمين "يمين" او "يسار" ....

او تعالج نص كbinary number وتسال اول bit هو "0" ام "1"

او تسأل عدة اسئلة مثل "هل لونه احمر" والجواب "نعم" او "لا"، وثم تسال "هل يحتوي على عجلات؟" وجوابه "نعم" او "لا"...وثم تصل leaf يحدد شيء (مثلا فيما اذا كانت سيارة رياضة ام شاحنة..الخ)

ملاحظة: يوجد

أعضاء في قائمة تجاهلي. لذا عدم ردي عليهم لا يدل على موافقتي الضمية لمحتويات مشاركاتهم.

sigsubway.png

#6

C77431:

اسمه random seed... هذا غير مطلوب هنا (لكن لست انا من اطى المتألق -1)

هذا مطلوب فقط عندما تريد انتاج high quality random number مع entropy عالي.... وهذا امر مرغوب به في التشفير cryptography

pseudo random number generators او PRND غالبا تأخذ input ويسمى بذرة او seed... وبواسطة تلك البذرة تنتج رقم random والذي بدوره ايضا المفروض يكون uniformly distributed

هناك طرق بالسوفتوير لتقوم باختيار تلك الseeds... مثلا اي algorithm ياخذ عدد الprocess و cpu utilization و memory utlization وثم يخرج رقم ما.. لكن مشكلته انه ربما يكون قابل للتخمين.. وهنا جانب ضعف بسيط

لذا احيانا الPRND تاخذ تلك الseed من hardware يحتوي على sensors تحتك مع الطبيعة مثل قياس المجال المغناطيسي للجاذبية او معدل الاشعاعات المنبعثة من الفضاء والشمس .. صحيح انه مكلف إلا انه اصعب للتخمين

كحل بديل للhardware.... ممكن تطلب من المستخدم تحريك الماوس.. لان هذا ايضا شيء غير متوقع..

يعني صعب جدا ان تخمن قيم X و Y لمكان مؤشر الماوس كما احركه انا

ليس فقط الماوس... بل ايضا اي شيء... مثلا في حالة gpg عند عملية انتاج المفاتيح public / private keys يطلب منك القيام بأي شيء.. سواء تحريك ماوس او compile برنامج.. أي شيء.

لكن عندما نأتي للbinary search فلا داعي اطلاقا لانتاج PRND عالي الجودة... PRND عالي الجودة مطلوب فقط في الcryptography

فيما يتعلق بالsearching methods ممكن نستخدم software seed generator

1

ملاحظة: يوجد

أعضاء في قائمة تجاهلي. لذا عدم ردي عليهم لا يدل على موافقتي الضمية لمحتويات مشاركاتهم.

sigsubway.png

#7
اقتباس
* الترتيب التصاعدي او التنازلي غير لازم. لذا اقترح تشيل النقطة رقم 1

* شرحك قد يؤدي إلى سوء فهم. لانك عندما تقسم الsearch space إلى اثنين، فأنت تذهب في احدى الاتجاهات . بينما شرحك يذهب في الاجتاهين.

* كذلك الbinary search ليس فقط بهذه الآلية... يعني انت هنا تقسم جميع العناصر إلى اثنين في هذه الحالة.. لكن ليس دائما تقسم الى قسمين.

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

أخي أفضل طرق البحث الثنائي أن يُقسم إلى نصفين ,

و لكن يبدو أن قصدك على طريقة تسمى ( البحث بالاستيفاء ) و هي أفضل من البحث الثنائي , تعتمد على حساب النسبة المئوية المفروضة لعنصر ما بين سلسلة عناصر مرتبة , بشرط أن تعرف الـmin , و الـmax لها قانون يمكنني إدراجه لك إن أردت

#8

ميزة الbinary search فوق الlinear search هو تقليل عدد الأسئلة

لذا عدد الاسئلة قلت من n إلى log n

وقضية الترتيب جيدة لزيادة سرعة الحصول على جواب سؤال البحث.

وانا الذي قلته لك ان "الترتيب التصاعدي او التنازلي غير لازم"

لانه مافرقت تصاعدي ام تنازلي.. كل ما في الأمر انه sorted بطريقة أو بأخرى

ممكن تتخيل الsorting كأنه function تسأله سؤال:

* هل كلمة apple يمين ام يسار؟

والsorting function يقوم بالإجابة سواء:

* بترتيب القائمة تصاعدي ام تنازلي (كما هو في مثالك)

* او ايضا ربما باستخدام dictionary يحتوي على ترتيب معين والذي هو ليس تصاعدي وليس تنازلي

فالدائرة ليست ضيقة على "تصاعدي ام تنازلي" لان الsorting algorithms كثيرة

والbinary search مجال تطبيقاته كبير، وبناء على كل تطبيق تختار sorting algorithm مناسبة

وليس شرطا ان يكون تصاعدي ام تنازلي

بالنسبة للقسمة الى نصفين..

كنت اتحدث عن القسمة بالتساوي من المنتصف كما هو المثال المعطى في الملف

ليس شرطا ان تكون القسمة الى نصفين من المنتصف

وكذلك ليس شرطا ان تكون القسمة بالتساوي

صحيح انه أحيانا يستحسن يكون في المنتصف... لكن ليس دائما.

مثلا للبحث عن كلمة apple، قد:

* تمسك من المنتصف وتسال يمين او يسار (كما هو في مثالك)

* او قد تسال هل أول bit هو 0 او 1 (حيث ان a في جدول ascii هو 01100001) وفي هذه الحالة لم تبدأ من المنتصف

ملاحظة: يوجد

أعضاء في قائمة تجاهلي. لذا عدم ردي عليهم لا يدل على موافقتي الضمية لمحتويات مشاركاتهم.

sigsubway.png

مواضيع مشابهة