خوارزمية البحث Jump Search Algorithm


المطلوب 
البحث والحصول على عنصر فى مصفوف مرتبة فلنفرض مثلًا اننا نملك مصفوفة تحتوي العناصر
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
وعدد عناصر هذه المصفوفة هو 16 عنصر
لنفرض اننا نريد ايجاد العدد 55
 بتخطى بعض العناصر ولنفرض انه يتخطى 4 عناصر فى كل مرة Jump Algorithm سيقوم
كالتالى
الخطوة الاولى : سيقفز من العنصر 0 الى العنصر 4
الخطوة الثانية : سيقفز من العنصر 4 الى العنصر 8
الخطوة الثالثة : سيقفز من العنصر 8 الى العنصر 12
الخطوة الثالثة : سيقفز من العنصر 12 الى العنصر 16
وعندما يجد ان العنصر فى الموقع 16 اكبر من 55 بالتالى يقوم بالرجوع  الى العنصر رقم 9
الخطوة الرابعة : يقوم بعمل بحث خطى فى العناصر من 9 حتى يجد العنصر 55
زمن التنفيذ
فى اسوء الحالات سنحتاج الى عدد مرات = عدد العناصر الكلى(n) / عدد العناصر التى نتخطاها فى المرة الواحدة (m)
بالاضافة الى تنفيذ m – 1 مقارنة اضافية فى البحث الخطى لايجاد العنصر
بالتالى عدد المرات الكلية فى اسوء الحالات هى n/m + m-1 وهذه القيمة تكون اصغير مايكن عندما تقريبًا
m = √n
الكود باستخدام python
def jump_search(numbers, value): # ايجاد عدد عناصر المصفوفة numbers_len = len(numbers) # ايجاد الجذر و تقريب الرقم الى عدد صحيح step = int(math.floor(math.sqrt(numbers_len))) prev = 0 while numbers[min(step, numbers_len)-1] < value: prev = step step += int(math.floor(math.sqrt(numbers_len))) if prev >= numbers_len: return -1 while numbers[prev] < value: prev += 1 if prev == min(step, numbers_len): return -1 if numbers[prev] == value: return prev return -1

شارك الموضوع

مواضيع ذات صلة