Dasturlashda chiziqli qidiruv

2022 May 05, 10:38 • Uzbek Developers (@uzbekdevs)

Dasturlashda eng ko’p qo’llaniladigan amallardan biri bu – ma’lumotlarni qidiruv. Qidiruvning birnechta asosiy variantlari mavjud bo’lib, ular uchun har xil algoritmlar yaratilgan.

Chiziqli qidiruv – ixtiyoriy funksiyaning qandaydir kesmadagi berilgan qiymatini qidirishga aytiladi. Bu algoritm oddiy algoritm hisoblanib, boshqa algoritmlardan, masalan binar qidiruvdan farqli tamoni funksiyaga hecha qanday cheklanish qo’yilmaydi va amalga oshirish oddiy hisoblanadi.

Chiziqli qidiruv algoritmi

Funksiya qiymatini izlash navbatdagi qiymatni (odatda chapdan o’nga argument oshishi tartibida amalga oshiriladi)oddiy taqqoslash orqali tekshiriladi. Masala ikki xil qo’yilishi mumkin: 1) Birinchi topilgan argumentni topish 2) Barcha argumentlarni topish.

Agar funkisya sifatida massiv argument sifatida massiv indeksi qo’llanilsa u holda chiziqli qidiruv natijasida berilgan massivdan bo’lgan shunday i indekslarni topish lozim.

Massiv: 45, 12 , 89, 12, -78, 12;

12 sonining pozitsiyalari 2, 4, 6;

Chiziqli qidiruv.

Oddiy chiziqli qidiruvda massivning har bir elementi bilan birma-bir tekshirib chiqiladiz.

int function LinearSearch (Array A, int L, int R, int Key);
begin
for X = L to R do
if A[X] = Key then
return X
return -1; 
end;

Bunda L va R o’zgruvchilar element qidiriladigan oraliq.

Har bir so’rovga O(n) amallar bajariladi. n – massiv elemenlari soni. Chiziqli qidiruv algoritmi qidirilayotgan interval kichik bo’lgan vaqtdagina effektiv bo’ladi.

#include <iostream>

using namespace std;

int a[10001];
void find(int a[], int left, int right, int k) {
bool found = 0;
for (int i = left; i <= right; i++) {
if (a[i]==k) {
found = 1;
cout<<i<<" ";
}
}
if (!found)
cout<<"-1";
cout<<endl;
}
int main() {
int n; 
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>a[i];//massiv elementlarini o'qitish
}
int k; // izlanayotgan son
cin>>k;
find(a, 1, n, k);
}
1934 marta ko'rildi
Uzbek Developers - uzbekdevs photo

Uzbek Developers

@uzbekdevs

Telegram Post

@uzbekdevs
“uzbekdevs.uz” saytida eʼlon qilingan materiallardan nusxa koʻchirish, tarqatish va boshqa shakllarda foydalanish faqat manba ko'rsatilishi orqali amalga oshirilishi mumkin.
© UzbekDevs