Algorithms/linear search

لو أردنا العثور على موقع عنصر معين في مصفوفة مكوّنة من عدد معيّن (n) من الأعداد الصحيحة فمن الطبيعي أنّ نبحث في عناصر المصفوفة واحدًا تلو الآخر ومن بداية المصفوفة إلى نهايتها إلى حين العثور على العنصر المطلوب. تسمى هذه الخوارزمية بالبحث الخطي. وإن عثر على العنصر المطلوب فإن عملية البحث تكون ناجحة successful search، وإن لم يُعثر على العنصر المطلوب تكون عملية البحث فاشلة unsuccessful search.

أمثلة

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

• C++‎:

#include <iostream> 
using namespace std; 
  
int search(int arr[], int n, int x) 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        if (arr[i] == x) 
            return i; 
    return -1; 
} 

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

• بايثون:

def search(arr, n, x):    
    for i in range (0, n): 
        if (arr[i] == x): 
            return i; 
    return -1; 
  
# اختبار الدالة السابقة
arr = [ 2, 3, 4, 10, 40 ]; 
x = 10; 
n = len(arr); 
result = search(arr, n, x) 
if(result == -1): 
    print("Element is not present in array") 
else: 
    print("Element is present at index", result);

• جافا:

class GFG 
{ 
public static int search(int arr[], int x) 
{ 
	int n = arr.length; 
	for(int i = 0; i < n; i++) 
	{ 
		if(arr[i] == x) 
			return i; 
	} 
	return -1; 
} 

// اختبار التابع السابق
public static void main(String args[]) 
{ 
	int arr[] = { 2, 3, 4, 10, 40 }; 
	int x = 10; 
	
	int result = search(arr, x); 
	if(result == -1) 
		System.out.print("Element is not present in array"); 
	else
		System.out.print("Element is present at index " + result); 
} 
}

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

إن كان العنصر المطلوب في الموقع i فإنّ عملية البحث الخطي ستبحث في i من العناصر لتعثر على العنصر المطلوب. أما إن لم يكن العنصر المطلوب موجودًا في المصفوفة فإن عملية البحث الخطي ستبحث في n من العناصر أي أنّها ستمرّ على جميع العناصر في المصفوفة، وهذه هي الحالة السوأى worst case.

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

تستخدم هذه الخوارزمية استخدامًا نادرًا وذلك لوجود خوارزميات أخرى تتفوق عليها تفوقًا واضحًا في الأداء مثل خوارزمية البحث الثنائي وجداول التقطيع.

انظر أيضًا

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

مصادر

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