الگوریتم جستجوی خطی (Linear Search)
در این بخش الگوریتم جستجوی خطی (Linear Search) را با یک مثال ساده بررسی خواهیم کرد. این الگوریتم جزء ساده ترین الگوریتم های جستجو و کم استفاده برای جستجو در مجموعه از داده ها است.
مسئله
با توجه به آرایه داده شده (arr[]) تابعی بنویسید که عنصر x را در آرایه جستجو کند.
مثال
Input : arr[] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}
x = 110;
Output : 6
Element x is present at index 6
Input : arr[] = {10, 20, 80, 30, 60, 50,110, 100, 130, 170}
x = 175;
Output : -1
Element x is not present in arr[].
حل
یک راه ساده برای حل این مسئله استفاده از الگوریتم جستجوی خطی یا همان linear search است.
- از سمت چپ ترین عنصر آرایه شروع کنید و هر یک از عناصر را با مقدار x مقایسه کنید.
- اگر مقدار x با یکی از عناصر آرایه مطابقت داشته باشد، اندیس آن عنصر را باز گردانید.
- اگر مقدار x با هیچ یک از مقادیر آرایه مطابقت نداشته باشد، مقدار -۱ را باز گردانید.
مثال
// C++ code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
#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;
}
امتحان کنید
خروجی:
Element is present at index 3
پیچیدگی زمانی الگوریتم جستجوی خطی برابر با O(n) است. این الگوریتم عملا زیاد مورد استفاده قرار نمی گیرد. زیرا الگوریتم هایی مانند الگوریتم جستجوی باینری (binary search) و یا hash tables در مقایسه با این الگوریتم خیلی سریع تر عمل می کنند.
نوشته الگوریتم جستجوی خطی (Linear Search) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.
