Algorithms/jump search

تستخدم عملية البحث القفزي Jump Search (يعرف كذلك بالبحث الكتلي Block search) مع المصفوفات المرتّبة، وتتلخّص فكرة هذه العملية في التحقق من عدد أقل من العناصر (مقارنة بالبحث الخطي) وذلك بالقفز عبر عناصر المصفوفة بخطوات ثابتة، بمعنى تجاوز بعض العناصر عوضًا عن البحث فيها كلّها.

فلو كانت لدينا المصفوفة arr[]‎ حجمها n وكتلة (عدد العناصر التي ستقفز فوقها) حجمها m. ستجري عملية البحث في المواقع arr[0], arr[m], [arr2m], ……arr[km]‎ وهكذا. وعند العثور على المجال (arr[km] < x < arr[(k+1)m]‎) نجري عملية بحث خطي بدءًا من الموقع km للعثور على العنصر المطلوب.

لنفترض أنّ لدينا المصفوفة التالية المكوّنة من 16 عنصرًا:

(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610)

تمرّ خوارزمية البحث القفزي بالخطوات التالية للعثور على العنصر 55، على فرض أنّ مقدار كل قفزة هو 4 عناصر:

1. القفز من الموقع 0 إلى الموقع 4.
2. القفز من الموقع 4 إلى الموقع 8.
3. القفز من الموقع 8 إلى الموقع 12.
4. لمّا كان العنصر في الموقع 12 أكبر من 55 فإن عملية البحث ستقفز إلى الوراء لتنتقل إلى الموقع 9.
5. إجراء عملية بحث خطّي من الموقع 9 إلى حين الوصول إلى العنصر 55.

حجم القفزة المثالي

في أسوأ الأحوال يجب القفز n/m مرة، وإن كانت قيمة آخر عنصر تم التحقّق منه أكبر من العنصر المراد البحث عنه، فعلينا إجراء m-1 عملية مقارنة إضافية في عملية البحث الخطي. وهكذا يصبح مجموع عمليات المقارنة في أسوأ الأحوال ‎((n/m) + m-1)‎، وتبلغ هذه الدالة أدنى قيمة لها عند m = √n؛ لذا فإنّ أفضل حجم للقفزة في هذه الخوارزمية هو m = √n.

ملاحظات

• تعمل هذه الخوارزمية مع المصفوفات المرتّبة فقط.
• الحجم المثالي للقفزة هو ‎(√n)‎ لذا فإنّ التعقيد الزمني لهذه الخوارزمية يبلغ ‎O(√n)‎.
• التعقيد الزمني لهذه الخورازمية يقع بين التعقيد الزمني للبحث الخطي O(n)‎ والتعقيد الزمني للبحث الثنائي O(Log n)‎.
• البحث الثنائي أفضل من البحث القفزي، ولكن البحث القفزي يتفوق في أنّ عملية البحث ترجع إلى الوراء مرة واحدة فقط (أما البحث الثنائي فقد يحتاج إلى الرجوع O(Log n)‎ مرة وذلك عندما يكون العنصر المراد البحث عنه هو العنصر الأصغر أو أنّه أصغر من أصغر العناصر)؛ لذا يستحسن استخدام البحث القفزي في الأنظمة التي يكون فيه الرجوع إلى الوراء عملية مكلفة.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية البحث القفزي في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

int jumpSearch(int arr[], int x, int n) 
{ 
	// حساب حجم القفزة
	int step = sqrt(n); 
	
    // العثور على الكتلة التي تحتوي على العنصر
    // (إن كان موجودًا أصلًا)
	int prev = 0; 
	while (arr[min(step, n)-1] < x) 
	{ 
		prev = step; 
		step += sqrt(n); 
		if (prev >= n) 
			return -1; 
	} 

	// إجراء عملية بحث خطي للعنصر المطلوب
    while (arr[prev] < x) 
	{ 
		prev++; 

		// إن وصلنا إلى الكتلة التالية أو إلى نهاية المصفوفة
        // فهذا يعني أن العنصر غير موجود
		if (prev == min(step, n)) 
			return -1; 
	} 
	// إن عُثر على العنصر المطلوب
	if (arr[prev] == x) 
		return prev; 

	return -1; 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 
				34, 55, 89, 144, 233, 377, 610 }; 
	int x = 55; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	
	// العثور على موقع العنصر المعطى باستخدام البحث القفزي
	int index = jumpSearch(arr, x, n); 

	// طباعة موقع العنصر المطلوب
	cout << "\nNumber " << x << " is at index " << index; 
	return 0; 
}

• بايثون:

import math 

def jumpSearch( arr , x , n ): 
	
	# حساب حجم القفزة
	step = math.sqrt(n) 
	
	# العثور على الكتلة التي تحتوي على العنصر 
	# (إن كان موجودًا أصلًا)
	prev = 0
	while arr[int(min(step, n)-1)] < x: 
		prev = step 
		step += math.sqrt(n) 
		if prev >= n: 
			return -1
	
	# إجراء عملية البحث الخطّي
	while arr[int(prev)] < x: 
		prev += 1
		
		# إن وصلنا إلى الكتلة التالية
        # أو وصلنا إلى نهاية المصفوفة، فهذا يعني أنّ العنصر غير موجود
		if prev == min(step, n): 
			return -1
	
	# إن عُثر على العنصر المطلوب
	if arr[int(prev)] == x: 
		return prev 
	
	return -1

# اختبار الدالة السابقة 
arr = [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 
	34, 55, 89, 144, 233, 377, 610 ] 
x = 55
n = len(arr) 

# العثور على موقع العنصر المعطى باستخدام البحث القفزي
index = jumpSearch(arr, x, n) 

# طباعة موقع العنصر المطلوب
print("Number" , x, "is at index" ,"%.0f"%index)

• جافا:

public class JumpSearch 
{ 
	public static int jumpSearch(int[] arr, int x) 
	{ 
		int n = arr.length; 

		// حساب حجم القفزة
		int step = (int)Math.floor(Math.sqrt(n)); 

    	// العثور على الكتلة التي تحتوي على العنصر
    	// (إن كان موجودًا أصلًا)
		int prev = 0; 
		while (arr[Math.min(step, n)-1] < x) 
		{ 
			prev = step; 
			step += (int)Math.floor(Math.sqrt(n)); 
			if (prev >= n) 
				return -1; 
		} 

		// إجراء عملية البحث الخطّي
		while (arr[prev] < x) 
		{ 
			prev++; 

			// إن وصلنا إلى الكتلة التالية أو إلى نهاية المصفوفة
	        // فهذا يعني أن العنصر غير موجود
			if (prev == Math.min(step, n)) 
				return -1; 
		} 

		// إن عثر على العنصر المطلوب
		if (arr[prev] == x) 
			return prev; 

		return -1; 
	} 

	// اختبار الدالة السابقة
	public static void main(String [ ] args) 
	{ 
		int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 
					34, 55, 89, 144, 233, 377, 610}; 
		int x = 55; 

		// العثور على موقع العنصر المعطى باستخدام البحث القفزي
		int index = jumpSearch(arr, x); 

		// طباعة موقع العنصر المطلوب
		System.out.println("\nNumber " + x + 
							" is at index " + index); 
	} 
}

انظر أيضًا

• البحث الخطي: البحث الخطّي Linear Search من أبسط خوارزميات البحث إذ أنّها تمر على عناصر المصفوفة واحدًا تلو الآخر بحثًا عن العنصر المطلوب.
• البحث الثنائي: تبحث خوارزمية البحث الثنائي Binary Search عن عنصر معين في مصفوفة مرتبة وذلك بتقسيمها باستمرار إلى نصفين والتحقق من وجود العنصر المراد البحث عنه في كلّ نصفٍ إلى أن تعثر على العنصر أو تصل إلى مصفوفة فارغة.
• البحث الاستكمالي: تعدّ خوارزمية البحث الاستكمالي Interpolation Search تحسينًا على البحث الثنائي في بعض الحالات، إذ تكون القيم موزّعة بانتظام في مصفوفة مرتبة فتجري هذه الخوارزمية عملية التحقّق في مواقع مختلفة بالاعتماد على قيمة المفتاح المراد البحث عنه.
• البحث الأسّي: تقسّم خوارزمية البحث الأسّي Exponential Search المصفوفة التي يجري البحث فيها إلى مصفوفات فرعية يزداد عدد العناصر فيها ازديادًا أسّيًا (1, 2, 4, 8.... وهكذا إلى حين الوصول إلى مصفوفة جزئية يكون فيها العنصر الأخير أكبر من العنصر المطلوب.

مصادر

• صفحة Jump Search في توثيق الخوارزميات في موقع GeeksforGeeks.