Algorithms/exponential search

قد يكون اسم هذه الخوارزمية مضلّلًا لأنّ التعقيد الزمني لها هو ‎O(Log n)‎، ومنشأ التسمية هو الطريقة المتّبعة في إجراء عملية البحث.

تضمّ عملية البحث الأسي خطوتين هما:

1. العثور على النطاق الذي يحتوي على العنصر المطلوب.
2. إجراء عملية بحث ثنائي على هذا النطاق.

تتلخص فكرة هذه الخوارزمية في البدء بمصفوفة جزئية حجمها 1، ومقارنة آخر عنصر فيها بالعنصر المطلوب، ثم الانتقال إلى مصفوفة حجمها 2، وإجراء المقارنة مرة أخرى، ثم الانتقال إلى مصفوفة حجمها 4 وإجراء المقارنة مرة أخرى وهكذا إلى حين الوصول إلى مصفوفة جزئية يكون فيها العنصر الأخير أكبر من العنصر المطلوب.

وبعد العثور على الموقع i (بعد مضاعفة قيمة i لعدة مرات) سنجزم حينئذٍ انّ العنصر المطلوب موجود بين الموقعين i/2 و i، وذلك لأنّنا لم نعثر على قيمة أكبر من قيمة العنصر المطلوب في الدورة السابقة.

عملية البحث الأسي مفيدة في عمليات البحث غير المحددة unbounded، حيث لا نهاية لحجم المصفوفة.

تؤدي هذه الخوارزمية عملًا أفضل من خوارزمية البحث الثنائي في المصفوفات المحددة bounded، وكذلك عندما يكون العنصر المراد البحث عنه قريبًا من العنصر الأول في المصفوفة.

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

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

• C++‎:

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

int binarySearch(int arr[], int, int, int); 

int exponentialSearch(int arr[], int n, int x) 
{ 
	// إن كان العنصر المطلوب موجودًا في الموقع الأول من المصفوفة فسنعيده ونوقف عمل الدالة
	if (arr[0] == x) 
		return 0; 

	// إيجاد النطاق الذي ستُجرى فيه عملية البحث الثنائي
    // وذلك بمضاعفة النطاق في كل دورة
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 

	// استدعاء دالة البحث الثنائية وتنفيذها على النطاق الناتج من الحلقة التكرارية
	return binarySearch(arr, i/2, min(i, n), x); 
} 

int binarySearch(int arr[], int l, int r, int x) 
{ 
	if (r >= l) { 
		int mid = l + (r - l) / 2; 

		// إن كان العنصر الموجود في وسط المصفوفة هو نفسه العنصر المعطى
        // فسنعيد العنصر نفسه
		if (arr[mid] == x) 
			return mid; 

		// إن كان العنصر أصغر من العنصر الموجود في وسط المصفوفة
		// فإنه سيكون موجودًا في النصف الأيسر من المصفوفة قطعًا
		if (arr[mid] > x) 
			return binarySearch(arr, l, mid - 1, x); 

		// وإلا فإنّ العنصر سيكون موجودًا في النصف الأيمن من المصفوفة قطعًا
		return binarySearch(arr, mid + 1, r, x); 
	} 

	// إن وصلنا إلى هنا فهذا يعني
    // أن العنصر غير موجود في المصفوفة
	return -1; 
} 

// اختبار الدالة السابقة
int main(void) 
{ 
int arr[] = {2, 3, 4, 10, 40}; 
int n = sizeof(arr)/ sizeof(arr[0]); 
int x = 10; 
int result = exponentialSearch(arr, n, x); 
(result == -1)? printf("Element is not present in array") 
				: printf("Element is present at index %d", 
													result); 
return 0; 
}

• بايثون:

def binarySearch (arr, l, r, x): 

	# التحقق من الحالة الأساس
	if r >= l: 
		mid = l + (r - l)/2

		# إن كان العنصر المعطى موجودًا في وسط المصفوفة فسنعيد العنصر نفسه
		if arr[mid] == x: 
			return mid 
		
		# إن كان العنصر المعطى أصغر من العنصر الموجود في وسط المصفوفة
        # فإنه سيكون موجودًا في النصف الأيسر من المصفوفة قطعًا
		elif arr[mid] > x: 
			return binarySearch(arr, l, mid-1, x) 

		# وإلا فإنّ العنصر سيكون موجودًا في النصف الأيمن من المصفوفة قطعًا
		else: 
			return binarySearch(arr, mid + 1, r, x) 

	else: 
		# العنصر غير موجود في المصفوفة
		return -1

def exponentialSearch(arr, n, x): 
	# إن كان العنصر المعطى موجودًا في بداية المصفوفة
    # فسنعيد العنصر نفسه ونوقف عمل الدالة
	if arr[0] == x: 
		return 0
		
	# إيجاد النطاق الذي ستُجرى فيه عملية البحث الثنائي
    # وذلك بمضاعفة النطاق في كل دورة
	i = 1
	while i < n and arr[i] <= x: 
		i = i * 2
	
	# استدعاء دالة البحث الثنائي وتنفيذها على النطاق الناتج من الحلقة التكرارية
	return binarySearch( arr, i / 2, 
						min(i, n), x) 
	

# اختبار الدالة السابقة
arr = [2, 3, 4, 10, 40] 
n = len(arr) 
x = 10
result = exponentialSearch(arr, n, x) 
if result == -1: 
	print "Element not found in thye array"
else: 
	print "Element is present at index %d" %(result)

• جافا:

import java.util.Arrays; 

class GFG 
{ 
	static int exponentialSearch(int arr[], 
								int n, int x) 
	{ 
		// إن كان العنصر المطلوب موجودًا في الموقع الأول من المصفوفة
        // نوقف عمل الدالة
        if (arr[0] == x) 
			return 0; 
	
		// إيجاد النطاق الذي ستُجرى فيه عملية البحث الثنائي 
		// وذلك بمضاعفة النطاق
		int i = 1; 
		while (i < n && arr[i] <= x) 
			i = i*2; 
	
		// استدعاء دالة البحث الثنائي وتطبيقها على النطاق الناتج من الحلقة التكرارية
		return Arrays.binarySearch(arr, i/2, 
								Math.min(i, n), x); 
	} 
	
	// اختبار الدالة السابقة
	public static void main(String args[]) 
	{ 
		int arr[] = {2, 3, 4, 10, 40}; 
		int x = 10; 
		int result = exponentialSearch(arr, arr.length, x); 
		
		System.out.println((result < 0) ? 
							"Element is not present in array" : 
							"Element is present at index " + 
							result); 
	} 
}

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

يبلغ التعقيد الزمني لعملية البحث الأسي المقدار O(Log n)‎.

انظر أيضًا

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

مصادر

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