DSA chiziqli qidiruv

Chiziqli qidiruv

Chiziqli qidiruv (Linear Search) algoritmi massiv bo‘ylab qidiradi va izlanayotgan qiymatning indeksini qaytaradi.

Chiziqli qidiruv algoritmi qanday ishlashini ko‘rish uchun yuqoridagi simulyatsiyani ishga tushiring.

Qiymat topilmaganda nima sodir bo‘lishini ko‘rish uchun 5 qiymatini topishga urinib ko‘ring.

Bu algoritm juda oddiy, uni tushunish va amalga oshirish oson.

Agar massiv allaqachon saralangan bo‘lsa, keyingi sahifada ko‘rib chiqadigan ancha tezroq ikkilik qidiruv (Binary Search) algoritmidan foydalangan ma’qul.

Saralash algoritmlari va qidirish algoritmlari o‘rtasidagi katta farq shundaki, saralash algoritmlari massivni o‘zgartiradi, qidirish algoritmlari esa massivni o‘zgarishsiz qoldiradi.

Qo‘lda bajarib ko‘rish

Chiziqli qidiruvni dasturlash tilida amalda amalga oshirishdan oldin, u qanday ishlashini yanada yaxshiroq tushunib olish uchun qidiruvni qo‘lda bajarib ko‘raylik. Biz 11 qiymatini qidiramiz.

1-qadam: Tasodifiy qiymatlardan iborat massivdan boshlaymiz.

2-qadam: Massivdagi birinchi qiymatni ko‘rib chiqamiz: u 11 ga tengmi?

3-qadam: 1 indeksidagi keyingi qiymatga o‘tamiz va teng yoki teng emasligini bilish uchun uni 11 bilan taqqoslaymiz.

4-qadam: 2 indeksidagi keyingi qiymatni tekshiramiz.

5-qadam: 3 indeksidagi keyingi qiymatga o‘tamiz. U 11 ga tengmi?

Topdik!

11 qiymati 3 indeksida topildi.

3 indeks pozitsiyasi qaytariladi.

Chiziqli qidiruv yakunlandi.

Yuqoridagi qadamlarni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Bu algoritm haqiqatan ham juda oddiy.

Massiv boshidan boshlab har bir qiymat biz topmoqchi bo‘lgan qiymat — 11 ga teng yoki teng emasligi tekshiriladi.

Qiymat topilganda qidiruv to‘xtatiladi va qiymat topilgan indeks qaytariladi.

Agar massiv bo‘ylab to‘liq qidirilib, qiymat topilmasa, -1 qaytariladi.

Chiziqli qidiruvni amalga oshirish

Chiziqli qidiruv algoritmini amalga oshirish uchun bizga quyidagilar kerak:

1. Qidiruv olib boriladigan qiymatlarga ega massiv.
2. Qidiriladigan maqsadli qiymat.
3. Massiv bo‘ylab boshidan oxirigacha o‘tadigan sikl.
4. Joriy qiymatni maqsadli qiymat bilan taqqoslaydigan va maqsadli qiymat topilsa, joriy indeksni qaytaradigan if operatori.
5. Sikldan keyin -1 ni qaytaring, chunki bu nuqtada maqsadli qiymat topilmaganini bilamiz.

Chiziqli qidiruv uchun natijaviy kod quyidagicha ko‘rinadi:

def linearSearch(arr, targetVal):
    for i in range(len(arr)):
        if arr[i] == targetVal:
            return i
    return -1

arr = [3, 7, 2, 9, 5]
targetVal = 9

result = linearSearch(arr, targetVal)

if result != -1:
    print("Value",targetVal,"found at index",result)
else:
    print("Value",targetVal,"not found")

Chiziqli qidiruvning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Insertion Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Agar chiziqli qidiruv \(n\) ta qiymatli massivda maqsadli qiymatni massivning birinchi qiymati sifatida topsa, faqat bitta taqqoslash kerak bo‘ladi.

Ammo agar chiziqli qidiruv maqsadli qiymatni topmasdan \(n\) ta qiymatli butun massiv bo‘ylab o‘tib chiqsa, \(n\) ta taqqoslash kerak bo‘ladi.

Demak, chiziqli qidiruvning vaqt murakkabligi

\[ O(n) \]

Agar chiziqli qidiruvga \(n\) ta qiymatli massivda qiymatni topish uchun qancha vaqt kerakligini chizsak, quyidagi grafikni olamiz:

Quyidagi simulyatsiyani massivdagi qiymatlarning turli sonlari uchun ishga tushiring va chiziqli qidiruvga \(n\) ta qiymatli massivda qiymatni topish uchun qancha taqqoslash kerakligini ko‘ring:

Yuqoridagi simulyatsiyada "Tasodifiy", "Kamayish tartibida" yoki "O‘sish tartibida" variantini tanlash chiziqli qidiruv tezligiga hech qanday ta’sir qilmaydi.

def linearSearch(arr, targetVal):
    for i in range(len(arr)):
        if arr[i] == targetVal:
          
    return -1