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

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

linear search algorithm 7271 تصویر

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

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

مسئله

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

مثال

حل

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

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

linear search 7271 تصویر

مثال

امتحان کنید

خروجی:

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

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

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