الگوریتم جستجوی خطی (Linear Search)

یکشنبه ۲۱ مهر ۱۳۹۸
بازدید ۱۰,۹۹۶ نفر
آرتین
(43 امتیاز از 9 رای)
Loading...

تصویر linear-search-algorithm_7271 الگوریتم جستجوی خطی (Linear Search)

الگوریتم جستجوی خطی (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[].

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 با هیچ یک از مقادیر آرایه مطابقت نداشته باشد، مقدار -1 را باز گردانید.

تصویر linear_search_7271 الگوریتم جستجوی خطی (Linear Search)

مثال

// 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;
}

// 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

1	Element is present at index 3

پیچیدگی زمانی الگوریتم جستجوی خطی برابر با O(n) است. این الگوریتم عملا زیاد مورد استفاده قرار نمی گیرد. زیرا الگوریتم هایی مانند الگوریتم جستجوی باینری (binary search) و یا hash tables در مقایسه با این الگوریتم خیلی سریع تر عمل می کنند.

الگوریتم ها - جستجوی دودویی