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

  • یکشنبه ۲۱ مهر ۱۳۹۸
  • بازدید ۹,۸۱۶ نفر

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

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

در این بخش الگوریتم جستجوی خطی (Linear Search) را با یک مثال ساده بررسی خواهیم کرد. این الگوریتم جزء ساده ‌ترین الگوریتم‌ های جستجو  و کم استفاده برای جستجو در مجموعه از داده ها است.

مسئله

با توجه به آرایه داده شده (arr[]) تابعی بنویسید که عنصر x را در آرایه جستجو کند.

مثال

حل

یک راه ساده برای حل این مسئله استفاده از الگوریتم جستجوی خطی یا همان linear search است.

  • از سمت چپ ترین عنصر آرایه شروع کنید و هر یک از عناصر را با مقدار x مقایسه کنید.
  • اگر مقدار x با یکی از عناصر آرایه مطابقت داشته باشد، اندیس آن عنصر را باز گردانید.
  • اگر مقدار x با هیچ یک از مقادیر آرایه مطابقت نداشته باشد، مقدار -1 را باز گردانید.

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

مثال

امتحان کنید

خروجی:

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

ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است