#  الگوریتم جستجوی خطی در پایتون

پایتون یکی از محبوب ترین و قدرتمندترین زبان های برنامه نویسی است. در این آموزش با linear search در پایتون آشنا می شویم. search تکنیکی است برای یافتن عنصر خاصی که در لیست داده شده وجود دارد یا نه.

دو نوع جستجوی پرکاربرد در پایتون وجود دارد:

• Linerar search
• Binary search

هر دو تکنیک به طور گسترده برای جستجوی یک عنصر در لیست داده شده استفاده می شوند.

 #  الگوریتم جستجوی خطی چیست؟

جستجوی خطی روشی برای یافتن عناصر در یک لیست است. به آن جستجوی متوالی(sequential search) نیز می گویند. این ساده ترین الگوریتم جستجو است زیرا عنصر مورد نظر را به صورت متوالی جستجو می کند.

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

بیایید با یک مثال الگوریتم جستجوی خطی را درک کنیم. قرار است در لیست زیر به دنبال عدد 7 بگردیم:

[1, 3, 5, 4, 7, 9]

برای پیدا کردن آیتم مورد نظر از ابتدای لیست شروع کرده و هر آیتم را مقایسه میکنیم:

تا زمانی که آیتم مورد نظر پیدا نشود، به جستجو ادامه میدهیم:

پیاده سازی الگوریتم خطی در پایتون به شکل زیر خواهد بود:

def linear_search(array, element):
    for i in range(len(array)):
        if array[i] == element:
            return i
    return -1

بیایید کد بالا را توضیح دهیم:

1. در خط اول یک تابع به نام linear_search ایجاد کردیم که دو آرگومان میگیرد. آرگومان اول یک دنباله و آرگومان دوم آیتمی است که به دنبال آن میگردیم.
2. در خط دوم به تعداد آیتم‌ های دنباله حلقه for خواهیم داشت.
3. در خط سوم هر آیتم دنباله را با آیتم مد نظر بررسی میکنیم.
4. در خط چهارم اگر آیتم مورد نظر پیدا شد، ایندکس آن را برمیگردانیم.
5. در خط پنجم اگر آیتم مورد نظر پیدا نشد، عدد منفی یک را برمیگردانیم.

 #  پیچیدگی زمانی الگوریتم جستجوی خطی

پیچیدگی زمانی الگوریتم جستجوی خطی به شکل زیر است:

• در بهترین حالت برابر با (1)O
• در بدترین حالت برابر با (n)O

الگوریتم جستجوی خطی برای لیست کوچک (کمتر از 100 آیتم) مناسب است زیرا هر آیتم را برای بدست آوردن عدد مورد نظر بررسی می کند. فرض کنید 10.000 آیتم وجود دارد و آیتم مورد نظر در آخرین ایندکس باشد، این کار با مقایسه با هر عنصر لیست زمان زیادی را صرف می کند.

برای رسیدن به نتیجه سریع می توانیم از الگوریتم جستجوی دودویی(binary) استفاده کنیم.