Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій кафедра програмного забезпечення Звіт з лабораторної роботи № 10 з дисципліни “Алгоритми і структури даних ” Львів 2008 Тема роботи: Ознайомлення із методами пошуку. Алгоритм бінарного пошуку. Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із методом бінарного пошуку. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу бінарного пошуку. ТЕОРЕТИЧНІ ВІДОМОСТІ Двійковий пошук (англ. Binary Search) — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння. Двійковий пошук суттєво швидший за лінійний, відносно простий в реалізації і загальновживаний. Обчислювальна складність алгоритму становить О(log2N). Текст програми #include<stdio.h> #include<conio.h> #include<stdlib.h> void main() { unsigned int mas[30000],mas2[4001],temp,a,beg=0,end=29999,ser=1,rez=0,i,j; clrscr(); for(i=0; i<30000; i++) mas[i]=rand()%4000; //-------------------------------------------------------------------- j=0; for (i=0;i<4001;i++) mas2[i]=0; for(i=0; i<30000; i++) mas2[mas[i]]++; for(i=0; i<=4001; i++) while(mas2[i]>0) { mas[j]=i; mas2[i]--; j++; } for(i=0; i<29999; i++) if(mas[i]>mas[i+1]) { puts("Ne sortuje!"); ser=0; break; } if(ser==1) puts("Sortuje!"); getch(); //------------------------------------------------------------------- puts("Vvedit chyslo vid 0 do 4000"); scanf("%i", &a); if ((a>4000)||(a<0)) { printf("Nekorectno vvedene chuslo"); getch(); return; } //------------------------------------------------------------------- while (rez==0 && ser>0 && ser<29999) { ser=(beg+end)/2; if(mas[ser]==a) rez=1; else if(mas[ser]<a) beg=ser; else end=ser; } //------------------------------------------------------------------- if(rez==0) printf("Shykanogo elementa nemaje!\n"); else printf("%i: %i\n", ser, mas[ser]); getch(); } Протокол роботи програми