15- الخوارزميات وبنى المعطيات – البحث الثنائي Algorithms and Data Structure – Binary Search

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

Algorithms and Data Structure – Binary Search
الخوارزميات وبنى المعطيات – البحث الثنائي

اليوم سنتحدث عن خوارزمية البحث الثنائي Binary search

البحث الثنائي عبارة عن خوارزمية بحث سريع مع تعقيد زمن تشغيل Ο (log n) – تم شرح موضوع التعقيد في درس سابق

خوارزمية البحث هذه تعمل على مبدأ فرق تسد divide and conquer – تم شرحه في درس سابق. لكي تعمل هذه الخوارزمية بشكل صحيح ، يجب أن تكون البيانات مرتبة – تم فرزها بشكل سابق

تقوم خوارزمية البحث الثنائي بالبحث عن عنصر معين من خلال مقارنة هذا العنصر بالعنصر الوسطي ضمن المجموعة. في حالة حدوث مطابقة ، فسيتم إرجاع فهرس العنصر الوسطي item index. أما اذا كان العنصر الوسطي أكبر من عنصر البحث، فسيتم البحث عن هذا العنصر ضمن المصفوفة الجزئية الواقعة الى يسار العنصر الأوسط. بخلاف ذلك ، يتم البحث عن العنصر في المصفوفة الجزئية الواقعة إلى يمين العنصر الأوسط. تستمر هذه العملية على المصفوفة الجزئية أيضًا حتى يتناقص حجم المصفوفات الجزئية إلى الصفر.

كيف تعمل خوارزمية البحث الثنائي binary search

من احد اهم الشروط للبحث الثنائي, ان تكون المعطيات مفروزة – مرتبة.

سنتعلم خوارزمية البحث الثنائي عن طريق مثال عملي.

فيما يلي مصفوفة مرتبة, وسنقوم بالبحث عن العنصر ذو القيمة 31 باستخدام البحث الثنائي.

في البداية يجب ان نحدد منتصف هذه المصفوفة باستخدام المعادلة التالية:

0+(9-0)/2 = 4

حيث ان 4 يمثل القيمة الصحيحة من 4.5, اذن 4 عبارة عن فهرس منتصف المصفوفة

سنقارن الان القيمة الموجودة في الدليل – فهرس index – رقم 4, مع القيمة التي يتم البحث عنها = 31.

نجد بأن القيمة 27 اصغر من القيمة التي يتم البحث عنها. اذن لا يوجد تطابق, وسيتم البحث من جديد ضمن المصفوفة الجزئية الواقعة الى يمين الفهرس الوسطي الحالي.

ستتغير الفهارس  كالتالي

Low = mid +1  اذ ان بداية المصفوفة الجزئية – الواقعة على اليمين – يبدأ من الفهرس الوسطي للمصفوفة الكلية , ويمثل الحد الادنى للفهرس

سنبحث عن الفهرس الوسطي للمصفوفة الجزئية من جديد

الفهرس الجديد = 7.

سنقارن القيمة 31 بالقيمة الموجودة ضمن الفهرس 7

نجد بان القيمة 34 اكبر من القيمة 31 التي يتم البحث عنها. بالتالي سيتم البحث ضمن المصفوفة الجزئية الواقعة على يسار القيمة عند الفهرس الحالي.

نقوم بحساب الفهرس الوسطي من جديد = 5

صورة

نقارن القيمة عن الفهرس index = 5  بقيمة البحث, نجد تطابق 31!

بالتالي فإن القيمة التي نبحث عنها ضمن هذه المصفوفة واقعة ضمن الفهرس رقم 5

 

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

بسودوكود الخوارزمية Pseudocode

الان حاول برمجة خوارزمية البحث الثنائي باحد لغات البرمجة التي تتقنها!

 

والى لقاء في حلقة جديدة نشرح فيها باللغة العربية خوارزمية البحث بالاستيفاء interpolation search

والى ذلك الحين استودعكم  الله والسلام عليكم ورحمة الله وبركاته

مع تحيات:

م. نور الصباحي

 

الترجمة	المصطلح
بنى المعطيات, او هياكل المعطيات	Data Structure
الخوارزميات	Algorithm
البحث الخطي	Linear Search
البحث الثنائي	Binary Search
دليل – فهرس	Index
البحث بالاستيفاء	interpolation Search
المؤشر الأمامي	Front Pointer
المؤشر الخلفي	Rear Pointer
سرعة المعالجة	Processor speed
الطلبات المتعددة	Multiple Request
التعقيد الزمني	Time complexity
التعقيد المكاني	Space complexity
التحليل المقار	Asymptotic Analysis
أفضل حالة	Best case
الحالة الوسيطية	Average case
اسوء حالة	Worst case
البحث الثنائي	Binary Search

 

References

https://www.tutorialspoint.com/data_structures_algorithms/