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

خوارزمية البحث الثنائى تعمل على مصفوفة مرتبة على سبيل المثال [1,4,5,6,7]

الهدف

البحث على عنصر معطى فى مجموعة من عناصر المصفوفة على ان تكون المصفوفة مرتبة

مثالًا

الدخل : [1,2,4,6,10] و 6

الخرج : 3 اي العنصر رقم 4 وقميته 6.

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

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

مثال

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

الكود باستخدام لغة Python

زمن التنفيذ لخوارزمية البحث الثنائى

log n