Chiziqli qidiruv
Chiziqli qidiruv
Chiziqli qidiruv (yoki ketma-ket qidiruv) eng oddiy qidiruv algoritmidir. U har bir elementni birma-bir tekshiradi.
{{ msgDone }}
Chiziqli qidiruv algoritmi qanday ishlashini ko‘rish uchun yuqoridagi simulyatsiyani bajaring.
Ushbu algoritm juda oddiy va tushunish va amalga oshirish oson.
Qanday ishlaydi:
- Massiv qiymatini boshidan qiymat bo‘yicha o‘ting.
- Biz izlayotgan qiymatga tengligini tekshirish uchun har bir qiymatni solishtiring.
- Agar qiymat topilsa, ushbu qiymatning indeksini qaytaring.
- Agar massiv oxiriga yetib, qiymat topilmasa, qiymat topilmaganligini bildirish uchun -1 ni qaytaring.
Agar massiv allaqachon saralangan bo‘lsa, keyingi sahifada ko‘rib chiqiladigan ancha tezroq ikkilik qidiruv (Binary Search) algoritmidan foydalanish yaxshiroqdir.
Pythonda chiziqli qidiruvni amalga oshirish
Pythondainlistda qiymat mavjudligini tekshirishning eng tezkor usuliinoperatoridan foydalanishdir.
Misol
Ro‘yxatda qiymat mavjudligini tekshiring:
mylist = [3, 7, 2, 9, 5, 1, 8, 4, 6]
if 4 in mylist:
print("Found!")
else:
print("Not found!")
O‘zingiz sinab ko‘ring »
Ammo agar siz qiymat indeksini topishingiz kerak bo‘lsa, chiziqli qidiruvni amalga oshirishingiz kerak bo‘ladi:
Misol
Ro‘yxatdagi qiymat indeksini toping:
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")
Misolni ishga tushirish »
Chiziqli qidiruv algoritmini amalga oshirish uchun bizga kerak:
- Qidiruv uchun qiymatlarga ega massiv.
- Qidiriladigan maqsadli qiymat.
- Massivni boshidan oxirigacha o‘tadigan sikl.
- Joriy qiymatni maqsadli qiymat bilan taqqoslaydigan va agar maqsadli qiymat topilsa, joriy indeksni qaytaradigan if-iborasi.
- Loopdan keyin -1 ni qaytaring, chunki bu nuqtada biz maqsadli qiymat topilmaganini bilamiz.
Chiziqli qidiruv vaqtining murakkabligi
Agar chiziqli qidiruv ishga tushsa va \(n\) qiymatlari bo‘lgan massivda maqsadli qiymatni birinchi massiv qiymati sifatida topsa, faqat bitta taqqoslash kerak bo‘ladi.
Agar chiziqli qidiruv butun \(n\) qiymatlar massivida maqsadli qiymatni topmasdan ishlasa, \(n\) taqqoslash kerak bo‘ladi.
Bu chiziqli qidiruv uchun vaqt murakkabligi: \( O(n) \)
Agar chiziqli qidiruvga \(n\) qiymatlar massividagi qiymatni topish uchun qancha vaqt kerakligini chizsak, quyidagi grafikni olamiz:
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!