Izlash algoritimlari. Chiziqli izlash
![2. Jadvalga ma’lumotni qo’yish.
Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) –
ma’lumot mavjud. Key – qidiruv argumenti. Unga rec - informatsion
yozuv mos qo’yiladi. Jadvaldagi ma’lumotlarning tuzilmasiga qarab
qidiruvning bir necha turlari mavjud.
2.2. Ketma-ket qidiruv algoritmi
Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz
yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda
ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan
boshlab, to katta adresgacha ketma-ket qarab chiqiladi. Massivda
ketma-ket qidiruv (search o’zgaruvchi topilgan element tartib
raqamini saqlaydi). Ketma-ket qidiruv algoritmi C++ tilida
quyidagicha bo’ladi:
int qidiruv(int key){
for (int i=0;i<="" p="">
if (k[i]==key) { search = i;return search;}
search = -1;
return search;
}}
Massivda ketma-ket qidiruv algoritmi samaradorligini bajarilgan
taqqoslashlar soni M bilan aniqlash mumkin. Mmin = 1, Mmax =
n. Agar ma’lumotlar massiv yacheykasida bir xil ehtimollik bilan
taqsimlangan bo’lsa, u holda
(n + 1)/2 bo’ladi.
Agar kerakli element jadvalda yo’q bo’lib, uni jadvalga
qo’shish lozim bo’lsa, u holda yuqorida keltirilgan algoritmdagi
oxirgi ikkita operator quyidagicha almashtiriladi.
n=n+1;
k[n-1]:=key;
r[n-1]:=rec;](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_9.png?v=1)
![elementni qo’shish yoki o’chirish o’rta hisobda barcha
elementlarning yarmini siljitishni talab qiladi. Ro’yhatda qidiruvning
samaradorligi taxminan massivniki bilan bir xil bo’ladi.
Teng bo’lish orqali qidiruv (ikkilik qidiruv) algoritmi
Faraz qilaylik, o’sish tartibida tartiblangan sonlar massivi berilgan
bo’lsin. Ushbu usulning asosiy g’oyasi shundan iboratki, tasodifiy
qandaydir AM element olinadi va u X qidiruv argumenti bilan
taqqoslanadi. Agar AM=X bo’lsa, u holda qidiruv yakunlanadi; agar
AM<="" p=""> bo’lgan barcha elementlar kelgusi qidiruvdan
chiqarib yuboriladi. Xuddi shuningdek, agar AM >X bo’lsa, u
holda indekslari M dan katta bo’lgan barcha elementlar kelgusi
qidiruvdan chiqarib yuboriladi. M ixtiyoriy tanlanganda ham taklif
qilinayotgan algoritm korrekt ishlaydi. Shu sababali M ni shunday
tanlash lozimki, tadqiq qilinayotgan algoritm samaraliroq natija
bersin, ya’ni uni shunday tanlaylikki, iloji boricha kelgusi
jarayonlarda ishtirok etuvchi elementlar soni kam bo’lsin. Agar biz
o’rtacha elementni, ya’ni massiv o’rtasini tanlasak yechim mukammal
bo’ladi. Misol uchun butun sonlardan iborat, o’sish bo’yicha
tartiblangan massivdan ikkilik qidiruv usuli yordamida key kalitga mos
elementni izlash dasturini ko’rib chiqamiz.
Dastur kodi:
#include
using namespace std;
int main(){
int n;cout<<"n=";cin>>n;
int k[n];
for(int i=0;i>k[i];
int key, search;
cout<<"qidirilayotgan elementni kiriting=";cin>>key;
int low = 0;
int hi = n-1; int j=0;](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_11.png?v=1)
![while (low <= hi){
int mid = (low + hi) / 2;j++;
if (key == k[mid]){
search = mid;
cout<<"qidirilayotgan element "<
"<
system("pause");
exit(0);
}
if (key < k[mid])
hi = mid - 1;
else low = mid + 1;
}
search=-1;
cout<
topilmadi\n";
system("pause");
}
Dastur natijasi
n=6
1 2 3 4 5 6
qidirilayotgan elementni kiriting=6 qidirilayotgan element 6 o'rinda
turibdi va u 3 ta solishtirishda toplidi.
2.4. Qidiruv jadvalini qayta tartibga keltirish
Umuman olganda, jadvalda har bir elementni qidirish
ehtimolligini qandaydir bir qiymat bilan izohlash mumkin. Faraz
qilaylik jadvalda qidirilayotgan element mavjud. U holda qidiruv](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_12.png?v=1)
![search=NULL;
exit(0);
Ishni bajarishga oid namuna
Talabalar ma’lumotlaridan – FIO va adresdan iborat jadval
berilgan. Binar qidiruvdan foydalanib TTJ da yashaydigan talabalar
ro’yhatini hosil qiling.
Algoritm
1. Jadvalga n ta talaba FIO va adreslarini kiritamiz.
2. Binar qidiruvni jadvalning birorta maydonida amalga
oshirish uchun jadvalni shu maydoni bo’yicha tartiblab olish
kerak. Shuning uchun masalaning qo’yilishida adresi TTJ bo’lgan
talabalarni topish kerakligi sababli jadval ma’lumotlarini adres
maydoni bo’yicha saralab olamiz. Masalani yechishda
to’g’ridan-to’g’ri tanlash orqali saralashdan foydalanilgan.
3. key kalitga mos elementni izlash chegaralarini aniqlab olamiz.
Dastlab u [0,n] oralig’ida, ya’ni low=0,hi=n.
4. Agar low<=hi bo’lsa, oraliq o’rtasini hisoblaymiz.
mid=(low+hi)/2
5. Agar mid o’rnida turgan talaba adresi TTJ bo’lsa, element
topildi, search=mid va 7-qadamga o’tiladi, aks holda keyingi qadamga
o’tiladi.
6. Agar “TTJ” so’zi alifbo bo’yicha mid o’rnida turgan talaba
adresi qiymatidan kichik bo’lsa, izlash quyi chegarasi o’zgaradi, ya’ni
mid o’rnida turgan elementdan bitta oldingi elementgacha olinadi, ya’ni
hi=mid-1. Aks holda, yuqori chegara o’zgaradi – mid dan keyingi
elementdan to oxirgi elementlar oralig’i olinadi, ya’ni low=mid+1. 4-
qadamga o’tiladi.
7. Agar topilgan elementdan oldin turgan elementning (mid-1)
ham adres maydoni TTJ bo’lsa, search--, ya’ni bitta oldingi
elementga o’tamiz va shu qadamni boshidan bajaramiz. Aks holda
keyingi qadamga o’tiladi. 8. Joriy (search ko’rsatayotgan) elementdan
boshlab adresi “TTJ” ga teng bo’lgan talaba ma’lumotlarini ekranga](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_16.png?v=1)
![chiqaramiz. Agar adresi “TTJ” dan farq qiladigan talaba chiqib qolsa,
algoritm tugallanadi.
Dastur kodi
#include
using namespace std;
int main(){
int n;cout<<"n=";cin>>n;
struct Guruh{
string fio,adres;
}talaba[n];
for(int i=0;i<="" p="">
cout<>talaba[i].fio;
cout<<"adres=";cin>>talaba[i].adres;
}
//jadval binar qidiruv olib boriladigan maydoni bo‘yicha
tartiblangan
//bo‘lishi kerak
for(int i=0;i<="" p="">
for(int j=i+1;j
if(talaba[i].adres>talaba[j].adres){
Guruh h=talaba[i];
talaba[i]=talaba[j];
talaba[j]=h;
}
for(int i=0;i<="" p="">
cout<
cout<<="" p="">](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_17.png?v=1)
![int low = 0,hi = n-1,search=-1,q=0;
string key="TTJ";
while(low<=hi){
int mid = (low + hi) / 2;
q++;
if (key == talaba[mid].adres){
search = mid;
break;
}
if (key < talaba[mid].adres)
hi = mid - 1;
else low = mid + 1;
}
if(search!=-1) cout<<"qidirilayotgan el "<
turibdi va "<
else {cout<
system("PAUSE");
return EXIT_SUCCESS;
}
while(talaba[search-1].adres==key) search--;
while(talaba[search].adres==key) {
cout<
"<
search++;
}
system("pause");](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_18.png?v=1)
![Algoritm
Chiziqli qidirish ( Massiv A, Qiymat x)
Qadam 1: Set i to 1
Step 2: if i > n then go to Qadam 7
Qadam 3: if A[i] = x then go to step 6
Qadam 4: Set i to i + 1
Qadam 5: Go to Step 2
Qadam 6: Print Element x Found at index i and go to step 8
Qadam 7: Print element not found
Qadam 8: Chiqish
Chiziqli qidish dasturi
Live demo
#include <stdio.h>
#define MAX 20
// array of items on which linear search will be conducted.
int intArray[MAX] =
{1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,55,66};
void printline(int count) {
int i;
for(i = 0;i <count-1;i++) {
printf("=");
}
printf("=\n");
}
// this method makes a linear search.
int find(int data) {](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_21.png?v=1)
![int comparisons = 0;
int index = -1;
int i;
// navigate through all items
for(i = 0;i<MAX;i++) {
// count the comparisons made
comparisons++;
// if data found, break the loop
if(data == intArray[i]) {
index = i;
break;
}
}
printf("Total comparisons made: %d", comparisons);
return index;
}
void display() {
int i;
printf("[");
// navigate through all items
for(i = 0;i<MAX;i++) {
printf("%d ",intArray[i]);
}
printf("]\n");
}
void main() {](https://docx.uz/documents/b9ba51ac-5587-4a33-a897-def5cd3f066c/page_22.png?v=1)
Izlash algoritimlari. Chiziqli izlash