Algorithms/interpolation search

البحث الاستكمالي

يبلغ التعقيد الزمني لعملية العثور على عنصر معين في مصفوفة ما باستخدام البحث الخطي المقدار O(n)‎، ويبلغ في البحث القفزي O(√ n)‎ والمقدار O(Log n)‎ في البحث الثنائي.

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

تحسب هذه الخوارزمية موقع التحقّق باستخدام الصيغة التالية:

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[]‎: المصفوفة التي ستجرى فيها عملية البحث

x: العنصر المراد البحث عنه

lo: أوّل موقع في المصفوفة arr[]‎.

hi: آخر موقع في المصفوفة arr[]‎.

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

1. حساب قيمة pos باستخدام الصيغة الواردة أعلاه وفي حلقة تكرارية.
2. إن كان العنصر المراد البحث عنه موجودًا في الموقع المحسوب، فيعاد الموقع وينتهي عمل الخوارزمية.
3. إن كان العنصر أقل من العنصر arr[pos]‎ فيُحسب الموقع في الجانب الأيسر من المصفوفة، وإلا فيحسب في الجانب الأيمن منها.
4. تكرر الخطوات السابقة إلى حين العثور على تطابق أو إلى حين الوصول إلى مصفوفة فارغة.

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

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

• C++‎:

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

int interpolationSearch(int arr[], int n, int x) 
{ 
	// إيجاد موقعي بداية المصفوفة ونهايتها
	int lo = 0, hi = (n - 1); 

	// لمّا كانت المصفوفة مرتّبة، فإنّ العنصر الموجود
    // في المصفوفة يجب أن يكون ضمن النطاق المحدد بحدي المصفوفة
	while (lo <= hi && x >= arr[lo] && x <= arr[hi]) 
	{ 
		if (lo == hi) 
		{ 
			if (arr[lo] == x) return lo; 
			return -1; 
		} 
		// حساب الموقع مع الأخذ بالحسبان التوزيع المنتظم للعناصر
		int pos = lo + (((double)(hi - lo) / 
			(arr[hi] - arr[lo])) * (x - arr[lo])); 

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

		// إن كان العنصر المطلوب أكبر من الموقع المحسوب فإن العنصر في النصف الأعلى
		if (arr[pos] < x) 
			lo = pos + 1; 

		// إن كان العنصر المطلوب أصغر من الموقع المحسوب فإن العنصر في النصف الأسفل
		else
			hi = pos - 1; 
	} 
	return -1; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 
				22, 23, 24, 33, 35, 42, 47}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	int x = 18; 
	int index = interpolationSearch(arr, n, x); 

	if (index != -1) 
		cout << "Element found at index " << index; 
	else
		cout << "Element not found."; 
	return 0; 
}

• بايثون:

def interpolationSearch(arr, n, x): 
	# تحديد موقعي بداية ونهاية المصفوفة
	lo = 0
	hi = (n - 1) 

	# لمّا كانت المصفوفة مرتّبة، فإنّ العنصر الموجود
    # في المصفوفة يجب أن يكون ضمن النطاق المحدد بحدي المصفوفة
	while lo <= hi and x >= arr[lo] and x <= arr[hi]: 
		if lo == hi: 
			if arr[lo] == x: 
				return lo; 
			return -1; 
		
		# حساب الموقع مع الأخذ بالحسبان التوزيع المنتظم للعناصر
		pos = lo + int(((float(hi - lo) /
			( arr[hi] - arr[lo])) * ( x - arr[lo]))) 

		# العثور على العنصر المطلوب
		if arr[pos] == x: 
			return pos 

		# إن كان العنصر المطلوب أكبر من الموقع المحسوب فإن العنصر في النصف الأعلى
		if arr[pos] < x: 
			lo = pos + 1; 

		# إن كان العنصر المطلوب أصغر من الموقع المحسوب فإن العنصر في النصف الأسفل
		else: 
			hi = pos - 1; 
	
	return -1

# اختبار الدالة السابقة
arr = [10, 12, 13, 16, 18, 19, 20, 21, \ 
				22, 23, 24, 33, 35, 42, 47] 
n = len(arr) 

x = 18 
index = interpolationSearch(arr, n, x) 

if index != -1: 
	print "Element found at index",index 
else: 
	print "Element not found"

• جافا:

class Test 
{ 
	static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 
										24, 33, 35, 42, 47}; 
	
	static int interpolationSearch(int x) 
	{ 
		// تحديد موقعي بداية ونهاية المصفوفة 
		int lo = 0, hi = (arr.length - 1); 
	
		// لمّا كانت المصفوفة مرتّبة، فإنّ العنصر الموجود
    	// في المصفوفة يجب أن يكون ضمن النطاق المحدد بحدي المصفوفة
		while (lo <= hi && x >= arr[lo] && x <= arr[hi]) 
		{		 

			if (lo == hi) 
			{ 
				if (arr[lo] == x) return lo; 
				return -1; 
			} 
		
			// حساب الموقع مع الأخذ بالحسبان التوزيع المنتظم للعناصر
			
			int pos = lo + (((hi-lo) / 
				(arr[hi]-arr[lo]))*(x - arr[lo])); 
	
			// العثور على العنصر المطلوب 
			if (arr[pos] == x) 
				return pos; 
	
			// إن كان العنصر المطلوب أكبر من الموقع المحسوب فإن العنصر في النصف الأعلى
			if (arr[pos] < x) 
				lo = pos + 1; 
	
			// إن كان العنصر المطلوب أصغر من الموقع المحسوب فإن العنصر في النصف الأسفل
			else
				hi = pos - 1; 
		} 
		return -1; 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int x = 18; 
		int index = interpolationSearch(x); 
		
		if (index != -1) 
			System.out.println("Element found at index " + index); 
			else
			System.out.println("Element not found."); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لهذه العملية المقدار O(log (log n))‎ إن كانت العناصر موزّعة بانتظام. أما في أسوأ الحالات فإن التعقيد الزمني قد يصل إلى O(n)‎.

انظر أيضًا

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

مصادر

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