Qidiruv usullarini tadqiq qilish

key kalitga mos elementni izlash chegaralarini aniqlab olamiz. Dastlab u [0,n] oralig‘ida, ya’ni low=0,hi=n.

Agar low<=hi bo‘lsa, oraliq o‘rtasini hisoblaymiz. mid=(low+hi)/2

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.

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.

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.

Joriy (search ko‘rsatayotgan) elementdan boshlab adresi “TTJ” ga teng bo‘lgan talaba ma’lumotlarini ekranga 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

cout<

cout<

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 "<

else {cout<

system("PAUSE");

return EXIT_SUCCESS;

}

while(talaba[search-1].adres==key) search--;

while(talaba[search].adres==key) {

cout<

search++; }

system("pause");

}