Chiziqli qidirish algoritmi
“The best place to hide a dead body is the second page of Google search.” — Anonymous
VII bo’lim. 1-dars.
Bugun sizlar bilan qidirish algoritmlarining eng soddasi bo’lgan chiziqli qidirish algoritmi haqida gaplashmoqchimiz. Bu algoritm chiziqli ma’lumotlar tuzilmalaridan (masalan, array) biror bir shart yoki qiymat bo’yicha element qidirishga mo’ljallangan.
Chiziqli qidirish algoritmi qanday ishlaydi
Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga ham oson.
- Arrayning birinchi elementidan tekshirish boshlanadi.
- Element olinadi va u berilgan shartga tekshirib ko’riladi.
- Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki shunchaki true) qaytariladi va algoritm tugaydi.
- Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladi
- Array tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1 yoki false…)
Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.
Algoritm implementatsiyasiga o’zingiz mustaqil harakat qilib ko’ring, yoki keyingi videodarsimizga o’ting.
Algoritm murakkabligi
Chiziqli qidirish algoritmining vaqt bo’yicha murakkabligi uning nomidan ham ma’lum, ya’ni chiziqli O(n). Ya’ni, eng yomon holat sifatida element array bo’lmagan holat qaraladi va bunda algoritm maksimum n ta qadam ish bajarishi kerak bo’ladi.
Xotira jihatidan, algoritm ortiqcha joy talab qilmaydi.
Chiziqli qidirish algoritmi ko’pincha real hayotdagi holatlar uchun ancha sekinlik qiladi. Shuning uchun ham bunday holatlarda undan boshqa tezroq ishlaydigan algoritmlar qo’llanilishi kerak bo’ladi (masalan, ikkilik qidirish). Lekin, bu algoritmning ham ikkilik qidirishdan o’ziga yarasha avfzal tomonlari mavjud. Bunga ikkilik qidirish (binary search) haqida gaplashgandan keyin batafsil to’xtalamiz.
Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing!
Manba: @AlgorithmUz telegram kanali
YouTube kanalimiz: Algorithms Uzbekistan
“Eng yaxshi reklama — bu mamnun mijoz tomonidan qilingan reklama” — Philip Kotler
