البحث الأسي

البحث الأسّي

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

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

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

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

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

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

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

• 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)‎.

تطبيقات عملية البحث الأسي

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

مصادر

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