الگوریتم جستجوی خَطی

مقدمه

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

اگه تابه‌حال دنبال یه وسیله توی یه کشو پر از وسایل گشته باشی، خیلی راحت می‌تونی درک کنی که الگوریتم جستجوی خطی چیه. مثلاً فکر کن می‌خوای یه خودکار خاص رو از یه کشوی پر از خودکار پیدا کنی. چیکار می‌کنی؟ شروع می‌کنی از اولین خودکار و یکی‌یکی به خودکارها نگاه می‌کنی تا به اون خودکار موردنظر برسی. این همون چیزیه که تو دنیای برنامه‌نویسی بهش میگن “الگوریتم جستجوی خطی” یا همون Linear Search به انگلیسی.

تاریخچه‌ای کوتاه از جستجو

اولین کامپیوترها طراحی شده بودن تا محاسبات عددی و پردازش‌های منطقی رو سریع‌تر انجام بدن، اما وقتی پای مدیریت داده‌های بیشتر و بیشتر به میون اومد، نیاز به تکنیک‌های جستجو و مرتب‌سازی ضروری شد. الگوریتم جستجوی خطی یکی از اولین و ساده‌ترین روش‌ها بود که به کمک برنامه‌نویسان اومد. چون کامپیوترها توانایی پردازش خطی داده‌ها رو داشتن، این روش خیلی زود تبدیل به استانداردی برای جستجوهای ساده و کوچک شد.

آموزش برنامه نویسی دارت

مقدمه زبان برنامه نویسی دارت در سال‌های اخیر رشد آهسته و پیوسته‌ای داشته؛ به همین خاطر این روزها این...

مشاهده دوره

جستجوی خطی چیه؟

خب، همونطور که از اسمش معلومه، الگوریتم جستجوی خطی یا Linear search یعنی ما به صورت خطی و یکی‌یکی توی یه لیست یا آرایه دنبال یه آیتم می‌گردیم. مثلاً وقتی یه لیست از عددها یا هر نوع داده دیگه‌ای داری و می‌خوای ببینی یه عدد خاص توی اون لیست هست یا نه، از اولین عدد شروع می‌کنی و تک‌تک چک می‌کنی تا به عدد مورد نظر برسی. اگه عدد رو پیدا کردی، ماموریتت تمومه! ولی اگه نه، باید همین‌جور ادامه بدی تا به آخر لیست برسی.

مثال ساده:

فرض کن یه لیست داریم که شامل این عدداست: [5, 3, 8, 6, 2, 7]

حالا می‌خوای ببینی عدد 6 تو این لیست هست یا نه. طبق الگوریتم Linear search، از اول لیست شروع می‌کنی:

آیا 5 برابر با 6 هست؟ نه!
آیا 3 برابر با 6 هست؟ نه!
آیا 8 برابر با 6 هست؟ نه!
آیا 6 برابر با 6 هست؟ بله! پس پیدا شد.

این ساده‌ترین حالت الگوریتم جستجوی خطی که احتمالاً تا اینجا برات روشن شده.

چرا جستجوی خطی؟

شاید با خودت بگی این روش یه مقدار ساده و حتی کند به نظر میاد، اما واقعیت اینه که جستجوی خـطی تو بعضی شرایط بهترین راهه. مثلاً وقتی:
داده‌ها مرتب نشده باشن: اگه لیستت یه ترتیب خاصی نداشته باشه (مثلاً صعودی یا نزولی نباشه)، جستجوی خطی یکی از راحت‌ترین و سریع‌ترین روش‌هاست. لیستت کوچیک باشه: وقتی تعداد داده‌ها کمه، جستـجوی خطی کارایی خوبی داره. مثلاً اگه 10 تا آیتم داری، دیگه لازم نیست بری سراغ روش‌های پیچیده‌تر.

کاربردهای عملی جستجوی خطی

بیایم نگاهی به این بندازیم که تو زندگی روزمره ما یا حتی تو دنیای واقعی، جستجوی خـطی کجاها استفاده میشه.

برنامه‌های مدیریت تماس و مخاطبین: فرض کن تو گوشی موبایلت یه لیست از مخاطبین داری. وقتی می‌خوای یکی از مخاطبینت رو پیدا کنی و لیستت کوچیک باشه، گوشی تو با یه روش ساده و سریع جستجوی خطی، مخاطب موردنظر رو پیدا می‌کنه.

پیدا کردن فایل تو کامپیوتر: وقتی دنبال یه فایل خاص توی پوشه‌ای پر از فایل‌ها می‌گردی، سیستم‌عاملت از یه روش مشابه جستجوی خطی برای جستجو استفاده می‌کنه. البته این روش وقتی لیست فایل‌ها کم باشه کارایی بیشتری داره.

وب‌سایت‌های کوچیک و دیتابیس‌های ساده: سایت‌هایی که دیتابیس‌های کوچیکی دارن یا کاربر زیادی ندارن، اغلب از جستجوی خـطی برای پیدا کردن اطلاعات توی دیتابیس استفاده می‌کنن. این به این دلیله که این نوع جستجو نیاز به منابع زیاد یا الگوریتم‌های پیچیده نداره.

برنامه‌های آموزشی و تمرینی: وقتی تو یه نرم‌افزار آموزشی برنامه‌نویسی یه الگوریتم ساده جستجو رو آموزش می‌بینیم، بیشتر اوقات جستجوی خطی اولین الگوریتمیه که معرفی میشه. چون این الگوریتم خیلی پایه‌ای و ساده‌ است.

مزایا و معایب این الگوریتم

همه‌ی الگوریتم‌ها یه سری خوبی‌ها و بدی‌ها دارن و جستـجوی خطی هم از این قاعده مستثنی نیست. بیایم یه نگاهی بندازیم به نقاط قوت و ضعف این روش.

مزایا:

ساده و قابل فهم: این روش خیلی راحته و هر کسی با هر سطحی از دانش برنامه‌نویسی می‌تونه اونو درک کنه و پیاده‌سازی کنه.

نیاز به مرتب‌سازی نداره: برخلاف خیلی از الگوریتم‌های جستجو که لیست رو باید مرتب کنی (مثل جستجوی دودویی)، این روش مستقیم میره سراغ داده‌ها و نیازی به مرتب‌سازی نداره.

انعطاف‌پذیری: می‌تونه برای هر نوع لیستی (مرتب یا نامرتب) استفاده بشه.

معایب:

کندی در لیست‌های بزرگ: وقتی لیستت خیلی بزرگ بشه، جستجوی خطی می‌تونه زمان زیادی ببره. چون مجبور میشی تک‌تک آیتم‌ها رو چک کنی.

کارایی پایین: وقتی لیست بزرگه، کارایی جستجوی خطی نسبت به روش‌های پیشرفته‌تر مثل جستجوی دودویی یا هشینگ کمتره.

الگوریتم جستجوی خطی به زبان‌های مختلف

حالا که فهمیدی الگوریتم چیه و چه مزایا و معایبی داره، بیایم ببینیم چطور می‌تونیم این الگوریتم رو تو کد پیاده‌سازی کنیم. این یه مثال ساده به زبان پایتون هست:

def linear_search(lst, target):

    # تو اینجا توی لیست lst دنبال مقدار target می‌گردیم

    for i in range(len(lst)):

        if lst[i] == target:

            return i  # آیتم پیدا شد
        
    return -1  # آیتم پیدا نشد


# مثال استفاده:

numbers = [5, 3, 8, 6, 2, 7]

result = linear_search(numbers, 6)

if result != -1:

    print(f"آیتم در موقعیت {result} پیدا شد.")

else:
    
    print("آیتم پیدا نشد.")

این کد خیلی ساده داره کار جستجوی خطی رو انجام میده. با یه حلقه for، یکی‌یکی عناصر لیست رو چک می‌کنه. اگه عنصر پیدا شد، موقعیتش رو برمی‌گردونه. اگه نشد، مقدار -1 رو برمی‌گردونه.

آموزش برنامه نویسی پایتون

آموزش پایتون : دوره‌ی آموزش پایتون بهترین انتخاب برای دانشجویان مبتدی در برنامه‌نویسی است، زیرا پایت...

مشاهده دوره

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

// تابع جستجوی خطی در دارت

int linearSearch(List<int> list, int target) {

  // حلقه برای جستجوی تک تک عناصر لیست

  for (int i = 0; i < list.length; i++) {

    if (list[i] == target) {

      return i; // اگه آیتم پیدا شد، ایندکس رو برمی‌گردونه
    }
  }

  return -1; // اگه آیتم پیدا نشد، -1 برمی‌گردونه
}

void main() {

  List<int> numbers = [5, 3, 8, 6, 2, 7];

  int target = 6;

  int result = linearSearch(numbers, target);

  if (result != -1) {

    print('آیتم پیدا شد در موقعیت: $result');

  } else {
    
    print('آیتم پیدا نشد.');
  }
}

بهینه‌سازی جستجوی خطی

جستجوی خطی به خودی خود ممکنه ساده باشه، اما هنوز هم روش‌هایی برای بهینه‌سازی این الگوریتم وجود داره که می‌تونه در شرایط خاص، عملکرد بهتری داشته باشه. بیایم یه سری از این روش‌ها رو بررسی کنیم:

1. توقف زودهنگام (Early Exit)

در حالت عادی، الگوریتم جستجوی خطی یکی‌یکی آیتم‌ها رو بررسی می‌کنه و ممکنه به آخر لیست برسه. اما اگه بدونی آیتم مورد نظرت به احتمال زیاد توی قسمت‌های ابتدایی لیست قرار داره، می‌تونی بعد از پیدا کردن اولین نتیجه، جستجو رو متوقف کنی.

برای مثال، فرض کن لیستی از محصولات داری و بیشتر کاربرها معمولاً دنبال محصولاتی می‌گردن که توی اول لیست هستن. با پیاده‌سازی “توقف زودهنگام”، بعد از پیدا کردن اولین مورد، دیگه بقیه لیست رو جستجو نمی‌کنی.

2. جستجوی همزمان (Parallel Linear Search)

تو سیستم‌های چند پردازشی و مدرن، می‌تونیم جستجوی خطی رو به چند بخش تقسیم کنیم و هر بخش رو به صورت همزمان جستجو کنیم. مثلاً اگه یه لیست بزرگ داری، می‌تونی اونو به چهار قسمت تقسیم کنی و هر قسمت رو تو یه پردازنده یا هسته جداگانه بررسی کنی. اینطوری سرعت جستجو می‌تونه خیلی بیشتر بشه.

مقایسه با جستجوی دودویی

ممکنه به گوشت خورده باشه که الگوریتم‌های دیگه‌ای هم برای جستجو وجود دارن. یکی از معروف‌ترین‌هاش جستجوی دودویی هست که وقتی لیست مرتب باشه، خیلی سریع‌تر از جستجوی خطی کار می‌کنه.

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

مثال: فرض کن لیستت اینجوری مرتب باشه: [2, 3, 5, 6, 7, 8]
اگه بخوای عدد 6 رو پیدا کنی، جستجوی دودویی از وسط لیست شروع می‌کنه و عدد 6 رو خیلی سریع‌تر از جستجوی خطی پیدا می‌کنه.

کارایی الگوریتم جستجوی خطی

وقتی از کارایی صحبت می‌کنیم، منظورمون زمان اجرای یه الگوریتم نسبت به اندازه‌ی داده‌هاست. تو جستجوی خطی، زمان اجرا به اندازه‌ی لیست بستگی داره. هر چی لیست بزرگ‌تر باشه، زمان بیشتری برای جستجو لازمه. به زبان فنی، پیچیدگی زمانی این الگوریتم O(n) هست. یعنی در بدترین حالت، باید تمام عناصر لیست رو بررسی کنی.

برای مثال، اگه لیستی با 1,000,000 آیتم داشته باشی و آیتم موردنظرت آخرین آیتم باشه، باید 1,000,000 بار بررسی انجام بدی تا بهش برسی.

چه زمانی از جستجوی خطی استفاده کنیم؟

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

لیست کوچیکه: اگه تعداد آیتم‌ها کم باشه (مثلاً 10 تا 20 آیتم)، جستجوی خطی روش مناسبیه.
لیست مرتب نیست: اگه داده‌هات مرتب نیستن و نمی‌خوای وقت بذاری برای مرتب‌سازی، جستجوی خطی بهترین انتخابه.
فضای حافظه مهمه: اگه برنامه‌ات بهینه‌سازی برای فضای حافظه مهمه و نمی‌خوای ساختارهای پیچیده‌ای مثل درخت یا هش‌جدول استفاده کنی، این الگوریتم گزینه خوبیه.

نتیجه‌گیری

الگوریتم جستجوی خطی یه روش ساده و ابتدایی برای پیدا کردن آیتم‌ها توی یه لیست نامرتبه. با اینکه تو لیست‌های بزرگ خیلی کارا نیست و می‌تونه زمان زیادی ببره، اما تو شرایط خاصی مثل لیست‌های کوچیک یا لیست‌های نامرتب، همچنان یه گزینه خوب به حساب میاد. این الگوریتم یکی از پایه‌ای‌ترین مفاهیم جستجو تو برنامه‌نویسیه و یادگیریش برای هر برنامه‌نویسی ضروریه.

آموزش لینوکس اِسِنشیالز

آموزش لینوکس 0 تا 100 که در یک دهه اخیر که دنیای فناوری به طرز شگفت‌آوری پیشرفت کرده است، هر کسی که ...

مشاهده دوره

اگه می‌خواید الگوریتم جستجوی خطی رو خیلی راحت و به زبان ساده یاد بگیرید، حتماً ویدیوی جدیدم رو که توی یوتیوب و آپارات گذاشتم ببینید! توی این ویدیو با یه روش خیلی ساده و جذاب توضیح دادم که چطوری با جستجوی خطی می‌تونید توی لیست‌ها دنبال چیزی بگردید و پیداش کنید. پس همین الان یه سر به کانال یوتیوب یا آپاراتم بزنید و ویدیو رو ببینید!

راستی، یادتون نره که حتماً پیج “نابغه‌ها” رو توی یوتیوب، اینستاگرام و بقیه شبکه‌های اجتماعی دنبال کنید تا اولین نفرایی باشید که از آموزش‌های جدید باخبر می‌شید! 🔔