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

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

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

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

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

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

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

binary-search1.png

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

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

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

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

binary_search_0

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

middle formula.JPG

0+(9-0)/2 = 4

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

binary_search_1

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

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

binary_search_2.jpg

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

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

middle formula 2

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

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

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

binary_search_3.jpg

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

binary_search_4.jpg

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

صورة

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

binary_search_6.jpg

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

 

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

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

pseudocode.JPG

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

 

والى لقاء في حلقة جديدة نشرح فيها باللغة العربية خوارزمية البحث بالاستيفاء 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/

 

 

 

Advertisements

, , , , , , , , ,

  1. أضف تعليق

اترك رد

Please log in using one of these methods to post your comment:

شعار وردبرس.كوم

أنت تعلق بإستخدام حساب WordPress.com. تسجيل خروج   /  تغيير )

Google+ photo

أنت تعلق بإستخدام حساب Google+. تسجيل خروج   /  تغيير )

صورة تويتر

أنت تعلق بإستخدام حساب Twitter. تسجيل خروج   /  تغيير )

Facebook photo

أنت تعلق بإستخدام حساب Facebook. تسجيل خروج   /  تغيير )

Connecting to %s

%d مدونون معجبون بهذه: