Maʼlumotlar tuzilmasi va algoritmlarda chiziqli qidirish haqida Chiziqli qidirish

Chiziqli qidirish vs Ikkilik qidirish

Umumiy jihatlar

Ikki algoritm uchun umumiy bo’lgan jihatlar, albatta, bu ularning qiladigan ishi va beradigan natijasida. Ya’ni ikki algoritm ham arraydan qandaydir elementni birorta shart asosida tekshiradi va element indeksini javob sifatida qaytaradi.
Bundan tashqari ikkala algoritmda ham ishlashi uchun qo’shimcha xotiradan joy talab qilinmaydi, ya’ni ikki algoritmning hotira bo’yicha murakkabliki O(1) ga teng.
Biz uchun esa hozir ularning farqli tomonlari muhimroq

Algoritmlarning farqli tomonlari

1. 
   Kiruvchi ma’lumot
   

Bu ikki algoritmning asosiy farqi, oldingi darslarimizda ham ko’p marta ta’kidlaganimizdek, ikkilik qidirish algoritmi ishlashi uchun array saralangan bo’lishi shart. Chiziqli qidirish algoritmida esa bu narsaga hojat yo’q. Aynan shu jihati bilan chiziqli qidirish algoritmi ikkilik qidirishdan ko’ra ustunlik qilishi mumkin. Chunki ba’zi holatlarda ma’lumot saralanmagan bo’lishi va uni saralash ko’proq vaqt olib qo’yishi mumkin.
2. Qidirish jarayoni
Chiziqili qidirish algoritmi elementni array boshidan tartib bilan qidiradi. Ikkilik qidirish algoritmida esa bu jarayon array o’rtasidan boshlanib turlicha davom etishi mumkin. Dasturlashda bu jarayon tasodifiy elementga murojaat (random access) deb ataladi. Bu narsa qidirish algoritmi ish bajarayotgan ma’lumot tuzilmasi uchun muhim. Chunki ba’zi tuzilmalarda tasodifiy elementga birdan murojaat qilishning iloji yo’q. Masalan, stack, queue, linked list va h.k.

Chiziqli qidirish ishlash tezligi:

1. 
   Eng yaxshi holatda: O(1)
   
2. 
   O’rtacha holatda: n(n+1)/2n = O(n)
   
3. 
   Eng yomon holatda: O(n)
   

Ikkilik qidirish ishlash tezligi:

1. 
   Eng yaxshi holatda: O(1)
   
2. 
   O’rtacha holatda: logn(logn+1)/2logn = O(logn)
   
3. 
   Eng yomon holatda: O(logn)