جستجوی خطی
جستجوی خطی: ساده‌ترین الگوریتم جستجو، پیاده‌سازی، تحلیل پیچیدگی و مقایسه با روش‌های دیگر
جستجوی خطی چیست؟
جستجوی خطی (Linear Search) یا ترتیبی: عناصر را از اول تا آخر یکی‌یکی بررسی می‌کنیم تا هدف پیدا شود یا لیست تمام شود. ساده‌ترین و عمومی‌ترین الگوریتم جستجو.
الگوریتم
- از عنصر اول شروع کن
- اگر برابر هدف بود، اندیس را برگردان
- وگرنه به عنصر بعدی برو
- اگر لیست تمام شد، «پیدا نشد» برگردان
پیاده‌سازی
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1 # پیدا نشدتحلیل پیچیدگی
| حالت | پیچیدگی | سناریو |
|---|---|---|
| بهترین | O(1) | هدف عنصر اول است |
| میانگین | O(n/2) = O(n) | هدف وسط لیست |
| بدترین | O(n) | هدف آخر است یا وجود ندارد |
مزایا و معایب
مزایا:
- روی هر داده‌ای کار می‌کند — مرتب نبودن مهم نیست
- پیاده‌سازی بسیار ساده
- برای لیست‌های کوچک کاملاً کافی
- به حافظه اضافی نیاز ندارد: O(1)
معایب:
- برای داده بزرگ کند است: O(n)
- از ساختار داده استفاده نمی‌کند
چه زمانی جستجوی خطی؟
- داده مرتب نیست (و مرتب‌کردن نمی‌ارزد)
- لیست کوچک است (زیر ~۱۰۰ عنصر)
- فقط یک‌بار جستجو می‌کنیم
- داده پشتیبانی از دسترسی تصادفی ندارد (مثل لیست پیوندی)
نکته: عملگر in پایتون روی لیست، دقیقاً جستجوی خطی است!
target in my_list همان O(n) را دارد.جمع‌بندی
- بررسی ترتیبی از اول تا آخر — O(n)
- مستقل از ترتیب داده؛ ساده و همه‌جا کارآمد برای داده کوچک
- برای داده بزرگ مرتب، جستجوی دودویی (مبحث بعد) انقلابی است
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.