Interpolation Search خوارزمية


المعطى مصفوف مرتبة من العناصر والمطلوب ايجاد عنصرمعين وليكون x فى المصفوفة  []arr
 
باستخدام Interpolation Search خوارزمية وهى نسخة محسنة من خوارزمية البحث الثنائى binary search  حيث ان خوارزمية البحث الثنائى تذهب دائمًا للعنصر الاوسط فى المصفوفة لتقارن العنصر المراد ايجاده به اما فى حالة Interpolation search فان موقع العنصر فى المصفوف سيختلف باختلاف قيمة العنصر الذى نبحث بمعنى انه اذا كان العنصر المراد البحث عن اقرب إلى العنصر الاخير فإن Interpolation search ستبدء بالبحث فى نهاية المصفوفة (وليس فى الوسط مثل binary searc ) اما اذا كان العنصر المراد البحث عنه اقرب إلى العنصر الاول فان الخوارزمية ستبدء البحث فى البداية ولإيجاد موقع العنصر المناسب عن طريق المعادلة التالية
 

arr[] ==> المصفوفة التى سنبحث فيها
x ==> العنصر الذى سنبحث عنه
lo ==> مكان اول عنصر فى المصفوفة

hi ==> مكان اخر  عنصر فى المصفوفة

 

 

خطوات عمل الخوارزمية

الخطوة الاولى : فى داخل اللوب نقوم نحسب pos عن طريق المعادلة السابقة
الخطوة الثانية : اذا كان العنصر الذى نبحث عنه مطابق للعنصر فى المصفوفة الذى مكانه pos ترجع الخوارزمية True
الخطوة الثالة : اذا كان العنصر الذى نبحث عنه اصغر من العنصر الذى مكانه pos فنحسب pos مره اخرى للجزء الشمال من المصفوفة اما اذا كان العنصر اكبر فنتعامل على الجزء اليمين من المصفوفة
التكرار حتى الوصول إلى العنصر المطلوب
 
الكود التقريبى باستخدام cpp

 

 
استدعاء الدالة

 

 

الخرج 

 

زمن التنفيذ هو ((o(loglog(n وفى اسوء حالة worst case هى (o(n

شاركه مع اصدقائك

كتب بواسطة admin

مؤسس مطور

التعليقات

اترك تعليقك

شاركنا بتعليقاتك حول الموضوع

*

Comments