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

linear search algorithm 7271 تصویر

الگوریتم جستجوی خطی (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 با هیچ یک از مقادیر آرایه مطابقت نداشته باشد، مقدار را باز گردانید.

linear search 7271 تصویر

مثال

// 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) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.

درباره نویسنده: administrator

ممکن است دوست داشته باشید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *