Maʼlumotlar tuzilmasi va algoritmlarda chiziqli qidirish haqida Chiziqli qidirish

Maʼlumotlar tuzilmasi va algoritmlarda chiziqli qidirish haqida

Chiziqli qidirish — juda oddiy qidirish algoritmi hisoblanadi. Ushbu turdagi qidiruvda barcha elementlar boʻyicha ketma-ket qidiruv amalga oshiriladi. Har bir element tekshiriladi va agar mos keladigan narsa topilgan boʻlsa, u qaytarib beriladi, aks holda qidirish maʼlumot toʻplash oxirigacha davom etadi.

Bu chiziqli qidirish algoritimida Big O = N; yani B(N)

N bu yerda qidirish jarayonida qidiryatgan malumotimizga nechi marta murojat qilinganidir

Masala: linearSearch(['a', 'b', 'c', 'd'], 'd') //’c’ (2 chi index da)

Yechim: const linearSearch = (list, item) => {

for (const [i, element] of list.entries()) {
if (element === item) {
return i
}
}
}

Binar Qidirish algoritmi

Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.
Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.
Binar qidiruv
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1)
Eng yomon ko'rsatkichi(vaqt): O(log n)
O'rtacha ko'rsatkichi(vaqt): O( log n)
Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.

Masalan:

function binary_Search(items, value){
var firstIndex = 0,
lastIndex = items.length - 1,
middleIndex = Math.floor((lastIndex + firstIndex)/2);

while(items[middleIndex] != value && firstIndex < lastIndex)
{
if (value < items[middleIndex])
{
lastIndex = middleIndex - 1;
}
else if (value > items[middleIndex])
{
firstIndex = middleIndex + 1;
}
middleIndex = Math.floor((lastIndex + firstIndex)/2);
}

return (items[middleIndex] != value) ? -1 : middleIndex;