البحث الخطي

لو أردنا العثور على موقع عنصر معين في مصفوفة مكوّنة من عدد معيّن (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; 
  
# Driver Code 
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)‎، ولهذا تسمّى هذه الخوارزمية بخوارزمية بالبحث الخطّي.

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

مصادر

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