Линейный поиск, линейный поиск с барьером, бинарный поиск, бинарный поиск без find

кафедра 304

Лабораторная работа № 1

по предмету «Алгоритмы и структуры данных»

Выполнила студентка 325 гр.

Старцева А. В.

Проверил  ст. преподаватель каф 304

Карташов А.В.

______________________

Линейный поиск, линейный поиск с барьером, бинарный поиск, бинарный поиск без find

Цель: реализовать линейный поиск, линейный поиск с барьером, бинарный поиск, бинарный поиск без find, и сравнить скорости их работы

Постановка задачи:

#include "stdafx.h"

#include <iostream>

#include "time.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

       setlocale(LC_ALL,"rus");

       clock_t t, t6;

       t=clock();

       const int n=100000;

       int a[n];

       for(int i=0; i<n;i++)

             a[i]=rand()%15;

       int k=345; //ключ, искомый элемент

       int i=0; // индекс массива

       cout<<"Линейный поиск"<<endl;

       while (i<n&&a[i]!=k) // пока не конец массива и эл-т не найден перейти на следующ.

             ++i;

       if(i<n)

             cout<<"Индекс искомого элемента: "<<i<<endl;

       else

             cout<<"Элемент не найден"<<endl<<endl;

       t6=clock();

       (double)t/CLOCKS_PER_SEC;

       cout<<"Время выполнения линейного поиска:  "<<(double)(t6-t)/CLOCKS_PER_SEC<<endl;

       clock_t t1,t7;

       t1=clock();

       cout<<"Линейный поиск с барьером"<<endl;

       int a1[n+1];

       for(int i=0; i<n;i++){

             a1[i]=rand()%15;

       a1[i+1]=k;}

       while (a1[i]!=k) // пока не конец массива перейти на следующ.

             ++i;

       cout<<"Индекс искомого элемента: "<<i<<endl<<endl;

       t7=clock();

       (double)t1/CLOCKS_PER_SEC;

       cout<<"Время выполнения линейного поиска с барьером:  "<<(double)(t7-t1)/CLOCKS_PER_SEC<<endl;

       clock_t t3,t8;

       t3=clock();

       cout<<"Бинарный поиск"<<endl;

       int l=0; //нижний индекс непросмотренной части массива

       int r=n-1; //верхний индекс непросмотренной части массива

       int m; //средний индекс непросмотренной части массива

       bool find=false; //find=true, если элемент найден

       while(l<r&&!find)

       {

             m=(l+r)/2;

             if(a[m]==k)

                    find=true;

             else if(a[m]<k)

                    l=m+1;

             else

                    r=m-1;

       }

       if(find)

             cout<<"Индекс искомого элемента: "<<m<<endl<<endl;

       else

             cout<<"Элемент не найден"<<endl<<endl;

       t8=clock();

       (double)t3/CLOCKS_PER_SEC;

       cout<<"Время выполнения бинарного поиска:  "<<(double)(t8-t3)/CLOCKS_PER_SEC<<endl;

       clock_t t4, t5;

       t4=clock();

       cout<<"Бинарный поиск без find"<<endl;

       int L=0; //нижний индекс непросмотренной части массива

       int R=n; //верхний индекс непросмотренной части массива

       int M; //средний индекс непросмотренной части массива

       while(L<R)

       {

             M=(L+R)/2;

             if(a[M]<k)

                    L=M+1;

             else

                    R=M;

       }

       if(R==n&&a[M]!=k)

             cout<<"Элемент не найден"<<endl<<endl;

       else

             cout<<"Индекс искомого элемента: "<<M<<endl<<endl;

       t5=clock();

       (double)t4/CLOCKS_PER_SEC;

       cout<<"Время выполнения бинарного поиска без find:  "<<(double)(t5-t4)/CLOCKS_PER_SEC<<endl;

       system("pause");

       return 0;

}

Результат:

Вывод:

1-линейный;
2-линейный с барьером;
3-бинарный;
4-бинарный без find;