جستجوی خطی
عضوها را یکی‌یکی از ابتدا با مقدار مورد جستجو مقایسه می‌کند تا آن را پیدا کند یا آرایه تمام شود.
ساده‌ترین جستجو: از ابتدای آرایه شروع کن و هر عضو را با target مقایسه کن. اولین جایی که برابر بود، اندیسش را برگردان؛ اگر به انتها رسیدی، −1.
- زمان:
O(n) - حافظه:
O(1) - CLRS، بخش ۲.۱
- جانسونباو، فصل ۴
- گریمالدی، فصل ۵
- هوروویتز–ساهنی، فصل ۱
هشت عدد نامرتب؛ ۲۷ در خانه‌ی ۵ پیدا می‌شود.
def linear_search(a, target):for i in range(len(a)):if a[i] == target:return ireturn -1
شروع اجرا
متغیرهای محلی
target27
نارنجی = در همین گام عوض شد
a list
3141592641275812
Call stack
- linear_search()خط 1
گام ۱ از ۱۴
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- comparisons
- ورودی فعلی (n=8)
نمایش به شکل جدول
| n | comparisons |
|---|---|
| 4 | 3.4 |
| 6 | 4.4 |
| 8 | 5.6 |
| 10 | 7.4 |
| 12 | 8.9 |
| 14 | 9.3 |
| 16 | 12.2 |
توضیح
ایده
ساده‌ترین جستجو: از ابتدای آرایه شروع کن و هر عضو را با target مقایسه کن. اولین جایی که برابر بود، اندیسش را برگردان؛ اگر به انتها رسیدی، −1.
هزینه
- بهترین حالت ۱ مقایسه، بدترین حالت
nمقایسه، و به‌طور متوسط حدودn/2:O(n). - برخلاف جستجوی دودویی به مرتب بودن آرایه نیاز ندارد و همیشه اولین تکرار را پیدا می‌کند.
در trace به چه چیزی نگاه کنی
- فلش
iروی آرایه جلو می‌رود و خط‌چین آبی ارتفاعtargetاست. - ورودی «در آرایه نیست» را با همان ورودی در جستجوی دودویی (بعد از مرتب کردن) مقایسه کن.