Chiziqli qidirish vs Ikkilik qidirish

Image source: Diffzi

“The best place to hide a dead body is the second page of Google search.” — Anonymous

VII bo’lim. 3-dars

O’tgan darslarimizda sizlar bilan chiziqli va ikkilik qidirish algoritmlari haqida gaplashib o’tgan edik. Bu darsda sizlar bilan bu ikki algoritmni solishtirib, umumiy jihatlari va farqlari haqida gaplashamiz.

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.

3. Solishtirish

Elementni qidirishda solishtirish jarayoni ham ikki xil bo’ladi. Chiziqli qidirish algoritmi faqat tenglikka asoslanadi. Ikkilik qidirish esa tenglik, katta yoki kichiklikka qarab, o’z ishini davom ettiradi.

4. Vaqt bo’yicha murakkablik

Ikkita bir xil vazifani bajaruvchi algoritmlarni solishtirayotgan paytda ularning ishlash tezligini solishtirib ko’rmasdan iloj yo’q albatta. Demak,

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)

Shunday qilib yuqorida sanab o’tganlarimiz chiziqli qidirish va ikkilik qidirish algoritmlari farqlari va umumiy jihatlari edi.

Keyingi darsimizda sizlar bilan satrdan qism satrni qidirishning oddiy algoritmini ko’rib chiqamiz.

Maqolani sizga yoqqan bo’lsa unga qarsak (clap) chalib qo’yishni esdan chiqarmang. 50 tagacha qarsak chalish mumkin. Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing! Bizning Telegram va YouTube kanallarimizga, hamda Mediumdagi sahifamizga obuna bo’lishni unutmang.

Muallif: Qudratxo’ja Musayev

Manba: @AlgorithmUz telegram kanali

YouTube kanalimiz: Algorithms Uzbekistan

“Eng yaxshi reklama — bu mamnun mijoz tomonidan qilingan reklama” — Philip Kotler