جستجوی خطی (Linear Search)
«جستجوی خطی (Linear Search)» ساده ترین الگوریتم جستجو است. لیست را از ابتدا تا انتها چک می کند. هر «عنصر (Element)» با «هدف (Target)» مقایسه می شود. اگر برابر بود، همان جا جواب می گیریم.
ایده اصلی جستجوی خطی
از خانه اول شروع می کنیم. سپس جلو می رویم و یکی یکی می سنجیم. اگر هدف را یافتیم، اندیس را برمی گردانیم. اگر به انتها رسیدیم و چیزی نبود، پاسخ «-1» است.
بررسی وجود یک مقدار با عملگر in
در پایتون، سریع ترین راهِ فهمیدن وجود مقدار، عملگر «in» است. این راه فقط وجود را می گوید، نه اندیس را.
mylist = [3, 7, 2, 9, 5, 1, 8, 4, 6]
if 4 in mylist:
print("Found!")
else:
print("Not found!")
پیاده سازی جستجوی خطی و برگرداندن اندیس
برای گرفتنِ اندیس، یک حلقه می زنیم. هر بار مقایسه می کنیم. با اولین برابری، اندیس را برمی گردانیم. اگر نبود، «-1» برمی گردانیم.
def linearSearch(arr, targetVal):
for i in range(len(arr)):
if arr[i] == targetVal:
return i
return -1
mylist = [3, 7, 2, 9, 5, 1, 8, 4, 6]
x = 4
result = linearSearch(mylist, x)
if result != -1:
print("Found at index", result)
else:
print("Not found")
گام های عملی
- لیست را آماده کن.
- مقدار هدف را تعیین کن.
- از اندیس صفر حلقه بزن.
- هر عنصر را با هدف مقایسه کن.
- یافت شد؟ اندیس را برگردان؛ وگرنه «-1» بده.
پیچیدگی زمانی
در بهترین حالت، اولین خانه برابر است؛ بنابراین یک مقایسه کافی است. در بدترین حالت، همه را می سنجیم. پس «پیچیدگی (Complexity)» زمانی، O(n) است.
نکته: اگر لیست مرتب است، جستجوی باینری خیلی سریع تر است.
پیوندها
مطالعه بیشتر در W3Schools: Linear Search، و صفحه Binary Search.
صفحه خودمان درباره گراف ها نیز مرتبط است. همچنین این صفحه «جستجوی خطی» را نشانه گذاری کن.
جمع بندی سریع
- ساده اما کند روی لیست بزرگ.
- به ترتیب می سنجد و جلو می رود.
- وجود؟ از
inاستفاده کن. - اندیس؟ حلقه بزن و برگردان.
- مرتب است؟ سراغ باینری برو.