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

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

یک مثال کاربردی برای درک بهتر:

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

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("آیتم پیدا نشد.")

۱. آیا 5 برابر 6 است؟ خیر.
۲. آیا 3 برابر 6 است؟ خیر.
۳. آیا 8 برابر 6 است؟ خیر.
۴. آیا 6 برابر 6 است؟ بله! آیتم پیدا شد و جستجو متوقف می‌شود.

داده‌ها مرتب نیستند:

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

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('آیتم پیدا نشد.');
  }
}

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

اندازه لیست کوچک است:

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

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

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

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

مزایا و معایب الگوریتم جستجوی خطی:

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

مزایا:

• سادگی و درک آسان: پیاده‌سازی و فهم این الگوریتم برای هر سطح از برنامه‌نویسان بسیار ساده است.
• عدم نیاز به مرتب‌سازی: برخلاف بسیاری از الگوریتم‌های جستجو که نیاز به لیست مرتب دارند، جستجوی خطی روی لیست‌های نامرتب هم کار می‌کند.
• انعطاف‌پذیری: می‌توان آن را برای جستجوی انواع داده‌ها در هر نوع ساختار خطی (آرایه، لیست پیوندی و ...) به کار برد.

معایب:

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

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

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

مثال پایتون (Python):

def linear_search(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("آیتم پیدا نشد.")

مثال دارت (Dart):

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('آیتم پیدا نشد.');
  }
}

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

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

جستجوی موازی (Parallel Linear Search):

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

مقایسه با جستجوی دودویی (Binary Search):

شاید نام جستجوی دودویی (Binary Search) را شنیده باشید. این الگوریتم در لیست‌های مرتب‌شده بسیار سریع‌تر از جستجوی خطی عمل می‌کند. در حالی که جستجوی خطی تک‌تک عناصر را بررسی می‌کند، جستجوی دودویی با تقسیم کردن مداوم لیست به دو نیم و حذف نیمی که آیتم در آن نیست، به سرعت به نتیجه می‌رسد. اما نکته کلیدی اینجاست که جستجوی دودویی فقط روی لیست‌های مرتب کار می‌کند، در حالی که جستجوی خطی نیازی به مرتب بودن لیست ندارد.

سوالات متداول (FAQ):