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

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

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

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

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

من دوست دارم آخر این آموزش فقط یک تابع رو حفظ نکرده باشی؛ باید بتونی وقتی با لیستی از اطلاعات روبرو می شی، تشخیص بدی آیا جستجوی خطی انتخاب خوبیه یا باید سراغ جستجوی دودویی، دیکشنری یا ابزارهای خود دیتابیس بری.

جستجوی خطی چیه و چرا بهش Linear Search می گن؟

اسم این الگوریتم ممکنه کمی رسمی به نظر برسه، ولی داستان خیلی ساده تر از این حرفاست. «خطی» یعنی عناصر رو یکی پس از دیگری جلو می ریم. اگه دنبال عدد 6 در لیست [5, 3, 8, 6, 2, 7] باشی، اول عدد ۵، بعد ۳، بعد ۸ و در نهایت ۶ رو بررسی می کنی. به محض رسیدن به عدد شش، جواب رو داری و لازم نیست بقیه لیست رو بخونی.

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

وقتی می گم اینجا چهار مقایسه انجام شده، منظورم چهار بار بررسی برابری با هدفه. اولین عنصر ایندکس 0 داره و عدد شش در ایندکس 3 قرار گرفته. پس اگه تابع ایندکس برگردونه، خروجی 3 هست؛ با اینکه شش، چهارمین عدد لیسته.

مثال مرحله به مرحله جستجوی خطی

بیا این بار سراغ یک مثال دقیق تر بریم. لیست [5, 3, 8, 6, 2, 7] رو داریم و هدفمون عدد 6 هست. من ترجیح می دم موقع یاد گرفتن الگوریتم، به جای اینکه فقط جواب آخر رو ببینیم، مسیر رسیدن به جواب رو هم ثبت کنیم.

در دور اول عدد ۵ رو با ۶ مقایسه می کنیم؛ برابر نیستن. دور دوم ۳ رو بررسی می کنیم و باز هم جواب نیست. دور سوم ۸ رو چک می کنیم. دور چهارم به ۶ می رسیم و همون لحظه کار تمومه. خیلی ساده. اینجا الگوریتم جستجوی خطی چهار بار مقدار رو بررسی کرده و خروجی ایندکس ۳ رو تحویل می ده.

حالا هدف رو از ۶ به ۹ تغییر بده. چی می شه؟ هیچ کدوم از شش عدد برابر ۹ نیستن، پس باید همه شش عضو رو بررسی کنیم و بعد اعلام کنیم مقدار پیدا نشد. این همون حالت بدیه که وقتی درباره سرعت الگوریتم حرف می زنیم، خیلی مهم می شه.

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

جستجوی خطی در پایتون؛ اولین کد واقعی

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

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

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1


numbers = [5, 3, 8, 6, 2, 7]
print(linear_search(numbers, 6))
print(linear_search(numbers, 9))

خروجی این کد اول 3 و بعد -1 هست. توی این مثال enumerate در هر دور هم مقدار عنصر رو بهمون می ده و هم ایندکسش رو. وقتی به هدف رسیدیم، return تابع رو همون جا تموم می کنه. وقتی تمام عناصر بررسی شدن و چیزی پیدا نشد، به return -1 می رسیم.

دقت کن این مثال جستجوی خطی در پایتون عددهای منفی رو هم پشتیبانی می کنه. مثلا اگه لیست [-5, 0, 3, -2] باشه و دنبال -2 بگردیم، خروجی ایندکس ۳ هست. مقدار -1 که برای «پیدا نشد» بر می گردونیم با خود داده ها قاطی نمی شه، چون خروجی ما ایندکسه و ایندکس واقعی لیست در این قرارداد از صفر شروع می شه.

یک نکته ظریف هم وجود داره: پایتون ایندکس منفی داره، ولی ما اینجا از اون قابلیت استفاده نمی کنیم؛ فقط -1 رو به عنوان علامت قراردادی نبودن نتیجه انتخاب کردیم. توی پروژه واقعی ممکنه ترجیح بدی None برگردونی تا این قرارداد واضح تر باشه.

اگر بخوای همه نتیجه های تکراری رو پیدا کنی چی؟

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

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

def find_all_indices(values, target):
    result = []
    for index, value in enumerate(values):
        if value == target:
            result.append(index)
    return result


numbers = [6, 3, 6, 8, 6]
print(find_all_indices(numbers, 6))
print(find_all_indices(numbers, 99))

نتیجه اول [0, 2, 4] و نتیجه دوم [] هست. اگه همه جواب ها رو می خوای، این روش طبیعی تر از اینه که برای هر نتیجه دوباره از ابتدای لیست جستجو کنی. فقط یادت باشه پیچیدگی فضای حافظه تابع دوم به تعداد جواب هایی بستگی داره که ذخیره می کنی.

آموزش جستجوی خطی در دارت

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

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

int linearSearch(List<int> values, int target) {
  for (var index = 0; index < values.length; index++) {
    if (values[index] == target) {
      return index;
    }
  }
  return -1;
}

void main() {
  final numbers = <int>[5, 3, 8, 6, 2, 7];
  print(linearSearch(numbers, 6));
  print(linearSearch(numbers, 9));
}

خروجی جستجوی خطی در دارت هم 3 و -1 هست. شرط index < values.length باعث می شه فقط سراغ ایندکس های معتبر بریم. اگه به اشتباه <= بذاری، ممکنه در مرحله آخر از محدوده لیست بیرون بزنی و خطا بگیری.

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

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

جستجوی خطی در روبی؛ کوتاه و خوانا

حالا بریم سراغ روبی. برای جستجوی خطی در روبی هم یه آرایه داریم و یک حلقه. این زبان به خاطر سینتکس خواناش برای تمرین حل مسئله جالبه. در مثال پایین از each_with_index استفاده می کنم؛ چیزی شبیه enumerate در پایتون که مقدار و ایندکس رو همزمان بهمون می ده.

وقتی هر سه کد رو کنار هم می ذاری، کم کم متوجه می شی «یادگیری الگوریتم» یعنی فهمیدن یک راه حل مستقل از شکل ظاهری زبان. این توانایی بعدها موقع خوندن کد دیگران یا کار با یک زبان تازه خیلی کمکت می کنه.

def linear_search(values, target)
  values.each_with_index do |value, index|
    return index if value == target
  end
  -1
end

numbers = [5, 3, 8, 6, 2, 7]
puts linear_search(numbers, 6)
puts linear_search(numbers, 9)

با اجرای این نمونه جستجوی خطی در روبی هم خروجی 3 و -1 می گیریم. اینجا return از متد خارج می شه، نه فقط از حلقه داخلی. اگه هیچ عددی برابر هدف نباشه، آخر متد مقدار -1 رو به صورت ضمنی بر می گردونه.

روبی توی دنیای بک اند و همین طور بعضی ابزارهای امنیتی هم استفاده می شه؛ ولی از همین یک مثال نباید نتیجه بگیری هر کسی بخواد وارد امنیت بشه، لزوما باید Ruby بلد باشه. اگه به این زبان علاقه داری، مسیر آموزش روبی نابغه ها رو ببین و مثال های بالا رو با سینتکس اون تمرین کن.

توابع آماده در پایتون، دارت و روبی بهترن یا کد دستی؟

حالا یک سؤال خیلی مهم: وقتی زبان برنامه نویسی خودش ابزار پیدا کردن مقدار رو داره، چرا باید الگوریتم جستجوی خطی رو دستی بنویسیم؟ جوابش اینه که برای یاد گرفتن منطق، کد دستی عالیه. ولی توی پروژه واقعی، معمولا اول سراغ روش استاندارد و خوانای خود زبان می ریم؛ مگر اینکه شرط جستجو یا نحوه گزارش نتیجه نیاز ویژه ای داشته باشه.

در پایتون عملگر in برای بررسی وجود مقدار مناسبه و متد index() جایگاه اولین نتیجه رو می ده؛ فقط اگه نتیجه پیدا نشه ValueError می ده. در دارت متد indexOf() ایندکس اولین تطابق یا -1 رو بر می گردونه. در روبی هم متد index اولین جایگاه رو می ده و در صورت نبودن نتیجه، nil بر می گردونه. پس اسم و قرارداد خروجی ها دقیقا یکسان نیست.

values = [5, 3, 8, 6, 2, 7]
print(6 in values)
print(values.index(6))
print(next((i for i, v in enumerate(values) if v == 9), None))

void main() {
  final values = <int>[5, 3, 8, 6, 2, 7];
  print(values.contains(6));
  print(values.indexOf(6));
  print(values.indexWhere((value) => value > 7));
}

values = [5, 3, 8, 6, 2, 7]
puts values.include?(6)
puts values.index(6)
p values.index(9)

این توابع آماده رو از روی شکل خروجیشون حفظ نکن؛ ازشون استفاده کن تا فرق سه نوع سؤال رو بفهمی: آیا مقدار وجود داره؟ اولین ایندکسش کجاست؟ یا اولین مقداری که یک شرط رو پاس می کنه کدومه؟ برای هر کدوم ممکنه یک روش متفاوت خواناتر باشه.

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

جستجو داخل اطلاعات واقعی؛ مثال سفارش فروشگاه

بذار یک مثال نزدیک تر به پروژه های ایران بزنیم. فرض کن توی یک پنل ساده، لیست چند سفارش رو از API گرفتی و الان می خوای اولین سفارش با شماره مشخص رو پیدا کنی. داده ها به شکل دیکشنری هستن؛ یعنی هر سفارش علاوه بر شماره، نام مشتری و وضعیت پرداخت هم داره. اینجا فقط مقایسه کردن دو عدد کافی نیست و باید یک ویژگی از هر آبجکت رو بررسی کنی.

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

orders = [
    {"id": 101, "customer": "Sara", "status": "paid"},
    {"id": 108, "customer": "Ali", "status": "pending"},
    {"id": 115, "customer": "Nima", "status": "paid"},
]


def find_first(items, predicate):
    for item in items:
        if predicate(item):
            return item
    return None


result = find_first(orders, lambda order: order["id"] == 108)
print(result)

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

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

فرق جستجوی خطی و جستجوی دودویی

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

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

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

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

پیچیدگی زمانی جستجوی خطی؛ O(n) یعنی چی؟

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

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

حافظه اضافی تابع معمولی جستجوی خطی فقط چند متغیره، پس O(1) حساب می شه. ولی اگه قرار باشه مثل مثال قبلی همه ایندکس های تکراری رو ذخیره کنی، خروجی می تونه تا O(n) فضا بگیره. این تفاوت بین الگوریتم پایه و نسخه ای که همه نتیجه ها رو جمع می کنه، مهمه.

عدد n/2 هنوز در Big O جزو O(n) حساب می شه، چون ضریب ثابت رو در رشد مجانبی کنار می ذاریم. از اون طرف نباید نتیجه بگیری یک حلقه پایتون با یک میلیون مقایسه در همه شرایط دقیقا یک ثانیه طول می کشه. نوع داده، پیاده سازی زبان، سخت افزار و هزینه هر مقایسه روی زمان واقعی اثر دارن.

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

چطور تعداد مقایسه های جستجو رو بشماریم؟

def linear_search_with_count(values, target):
    comparisons = 0
    for index, value in enumerate(values):
        comparisons += 1
        if value == target:
            return index, comparisons
    return -1, comparisons


numbers = [5, 3, 8, 6, 2, 7]
print(linear_search_with_count(numbers, 6))
print(linear_search_with_count(numbers, 9))

خروجی این مثال به ترتیب (3, 4) و (-1, 6) هست؛ یعنی هم ایندکس پیدا شده رو داریم، هم تعداد دفعاتی که واقعا مقایسه انجام شده. این روش برای تست آموزشی الگوریتم جستجوی خطی خیلی بهتر از اینه که صرفا زمان اجرای یک مثال کوچیک رو با ساعت سیستم اندازه بگیری، چون زمان اجرا برای داده خیلی کم می تونه تحت تاثیر نویز محیط قرار بگیره.

بهینه سازی جستجوی خطی؛ چه چیزی واقعا کمک می کنه؟

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

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

یه حرف دیگه هم زیاد شنیده می شه: «جستجوی خطی رو موازی کن، حتما سریع تر می شه». نه همیشه. برای لیست های کوچیک، هزینه ساخت کارگرها و انتقال داده می تونه از خود جستجو بیشتر باشه. در پایتون هم بحث GIL و تفاوت Thread و Process مطرحه. پس تا وقتی اندازه داده و هزینه واقعی کار رو اندازه نگرفتی، موازی سازی رو نسخه جادویی ندان.

اگه مسیرت امنیت و شبکه باشه، همین مهارت تحلیل عملکرد برای بررسی لاگ ها، پیدا کردن الگو و تحلیل داده مفیده. اما برای مجموعه داده های خیلی بزرگ معمولا از ابزارهای ایندکس گذاری، موتورهای جستجو یا پردازش تخصصی استفاده می کنن؛ با یک حلقه ساده همه مسائل حل نمی شه.

مزایا و محدودیت های الگوریتم جستجوی خطی

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

ضعف اصلی هم روشنه: در بدترین حالت مجبور می شی همه عناصر رو بررسی کنی. اگه لیست دائم بزرگ تر می شه یا یک جستجوی ثابت در ثانیه هزاران بار تکرار می شه، باید درباره ساختار داده و نوع الگوریتم تجدید نظر کنی. این ایراد به معنی بی فایده بودن جستجوی خطی نیست؛ یعنی این روش هم مثل هر ابزار دیگه جایی برای استفاده داره.

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

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

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

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

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

سه تمرین برای اینکه الگوریتم واقعا یادت بمونه

تمرین اول: در پایتون تابعی بنویس که فقط بگه یک مقدار داخل لیست وجود داره یا نه و به جای ایندکس، True یا False برگردونه. تمرین دوم: تابع رو برای نام های تکراری تغییر بده تا همه جایگاه ها رو برگردونه. تمرین سوم: همین نسخه رو با زبان دارت یا روبی بازنویسی کن و برای لیست خالی، تک عضوی و مقدار ناموجود تست بنویس.

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

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

پرسش های متداول درباره Linear Search

جمع بندی: از یک حلقه ساده تا حل مسئله واقعی

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

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

برای ادامه همین مسیر، پیشنهاد می کنم بعد از این درس جستجوی دودویی و مرتب سازی حبابی رو هم ببینی. اگه موقع کدنویسی به حلقه، تابع یا ساختمان داده گیر کردی، برگرد سراغ آموزش پایتون یا دارت و همون قسمت رو تمرین کن. مهم این نیست زود از مقاله رد بشی؛ مهم اینه بتونی بدون نگاه کردن به جواب، خودت تابع جستجو رو دوباره بنویسی.

ویدیوی آموزش جستجوی خطی

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

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