Ikkilik qidiruv va chiziqli qidiruv
Chiziqli qidiruv, shuningdek ketma-ket qidiruv deb ham ataladigan eng oddiy qidiruv algoritmi. Ro'yxatdagi har bir elementni tekshirish orqali ro'yxatdagi belgilangan qiymatni qidiradi. Ikkilik qidiruv, shuningdek, tartiblangan ro'yxatda belgilangan qiymatni topish uchun ishlatiladigan usul. Ikkilik qidiruv usuli tekshirilgan elementlar sonini (har bir iteratsiyada) ikki barobarga qisqartiradi, bu esa berilgan elementni roʻyxatda topish uchun ketadigan vaqtni qisqartiradi.
Chiziqli qidiruv nima?
Chiziqli qidiruv eng oddiy qidirish usuli boʻlib, u roʻyxatdagi har bir elementni belgilangan elementni topmaguncha ketma-ket tekshiradi. Chiziqli qidirish usuliga kirish ketma-ketlik (masalan, massiv, to'plam yoki qator) va izlanishi kerak bo'lgan elementdir. Belgilangan element taqdim etilgan ketma-ketlikda bo'lsa, chiqish rost yoki ketma-ketlikda bo'lmasa, noto'g'ri bo'ladi. Ushbu usul ko'rsatilgan element topilmaguncha ro'yxatdagi har bir elementni tekshirganligi sababli, eng yomon holatda u kerakli elementni topishdan oldin ro'yxatdagi barcha elementlardan o'tadi. Chiziqli qidiruvning murakkabligi o(n). Shuning uchun katta ro'yxatlardagi elementlarni qidirishda foydalanish juda sekin deb hisoblanadi. Lekin bu juda oddiy va amalga oshirish osonroq.
Ikkilik qidiruv nima?
Ikkilik qidiruvi tartiblangan roʻyxatdagi belgilangan elementni topish uchun ham qoʻllaniladigan usuldir. Bu usul qidirilayotgan elementni ro'yxat o'rtasida joylashgan elementlar bilan solishtirishdan boshlanadi. Agar taqqoslash natijasida ikkita element teng ekanligini aniqlasa, usul to'xtaydi va elementning o'rnini qaytaradi. Agar qidirilayotgan element o'rta elementdan katta bo'lsa, tartiblangan ro'yxatning faqat pastki yarmidan foydalanib usulni qaytadan boshlaydi. Agar qidirilayotgan element o'rta elementdan kichik bo'lsa, tartiblangan ro'yxatning faqat yuqori yarmidan foydalanib usulni qaytadan boshlaydi. Agar qidirilayotgan element ro'yxatda bo'lmasa, usul shuni ko'rsatadigan noyob qiymatni qaytaradi. Shuning uchun ikkilik qidiruv usuli taqqoslash natijasiga qarab (har bir iteratsiyada) taqqoslanadigan elementlar sonini ikki baravar kamaytiradi. Shunday qilib, ikkilik qidiruv logarifmik vaqtda ishlaydi va natijada o(log n) oʻrtacha ish koʻrsatkichi boʻladi.
Ikkilik qidiruv va chiziqli qidiruv oʻrtasidagi farq nima?
Garchi chiziqli qidiruv ham, ikkilik qidiruv ham qidiruv usullari boʻlsa-da, ular bir qancha farqlarga ega. Ikkilik qidiruv saralangan ro'yxatlarda ishlayotgan bo'lsa, chiziqli qidiruv saralanmagan ro'yxatlarda ham ishlashi mumkin. Ro'yxatni saralash odatda n log n ga teng o'rtacha holatlar murakkabligiga ega. chiziqli qidiruv ikkilik qidiruvga qaraganda sodda va oson amalga oshiriladi. Biroq, chiziqli qidiruv o (n) o'rtacha ish ko'rsatkichi tufayli katta ro'yxatlar bilan foydalanish uchun juda sekin. Boshqa tomondan, ikkilik qidiruv katta ro'yxatlar bilan ishlatilishi mumkin bo'lgan samaraliroq usul hisoblanadi. Ammo ikkilik qidiruvni amalga oshirish juda qiyin bo'lishi mumkin va tadqiqot shuni ko'rsatdiki, ikkilik qidiruv uchun aniq kod yigirmata kitobdan faqat beshtasida topilishi mumkin.
