Лекция № 10

Тема: «Алгоритмы поиска. Поиск в линейных структурах»

 

План лекции

1. Поиск в линейных структурах

2. Линейный поиск

3. Бинарный поиск

 

1. Поиск в линейных структурах

Поиск – процесс отыскания информации во множестве данных (обычно представляющих собой записи) путем просмотра специального поля в каждой записи, называемого ключом. Целью поиска является отыскание записи (если она есть) с данным значением ключа.

Поиск – одно из наиболее часто встречающихся в программировании действий. Существует множество различных алгоритмов этого действия, принципиально зависящих от способа организации данных.

При дальнейшем рассмотрении поиска в линейных структурах определим, что множество данных, в котором производится поиск, описывается как массив фиксированной длины:

A: array[1..n] of ItemType;

Обычно тип ItemType описывает запись с некоторым полем, играющим роль ключа, а сам массив представляет собой таблицу. Так как здесь рассматривается, прежде всего, сам процесс поиска, то будем считать, что тип ItemType включает только ключ (т.е. используем одномерный массив).

 

2. Последовательный (линейный) поиск

Последовательный поиск – самый простой из известных. Суть его заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

Именно так поступает человек, когда ищет что-то в неупорядоченном множестве. Таким образом, данный алгоритм можно применять тогда, когда нет никакой дополнительной информации о расположении данных в рассматриваемой последовательности.

Пусть дан массив элементов A и ключ b. Для b необходимо найти совпадающий с ним элемент массива А. Линейный поиск подразумевает последовательный просмотр всех элементов массива А в порядке их расположения, пока не найдется элемент равный b. Если заранее неизвестно, имеется данный элемент в массиве или нет, то необходимо следить за тем, чтобы поиск не вышел за границы массива, что достигается использованием стоппера (барьерного элемента). Рассмотрим 2 примера:

 

1)      без использования стоппера

 

#include <iostream.h>

#include <iomanip.h>

#include <ctime>

//прототип подпрограммы заполнения массива

void vvod(int n, int a[]);

//прототип подпрограммы вывода элементов массива

void vivod(int n, int a[]);

//прототип подпрограммы линейного поиска

void LineSearch(int n, int a[],int b);

 

int main()

{

     system("chcp 1251>nul");

     int n,*a, i;      

     cout<<"Введите размер массива n=";

     cin>>n;

     a=new int [n];

     vvod(n,a);

     vivod(n,a);

     int b;    //переменная для хранения ключа

     cout<<"Введите ключ "; cin>>b;

     LineSearch(n,a,b); 

     //освобождение памяти из массива

     delete[] a;

     system("pause");

     return 0;

}

//реализация подпрограммы заполнения массива

void vvod(int n, int a[])

{

     int a1,b1,i;

     cout<<"Введите диапазон заполнения масссива: ";

     cin>>a1>>b1;

     cout<<"Исходный массив:"<<endl;

     srand(time(NULL));

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

     {

          a[i]=(b1-a1)*rand()/32767+a1;

     }

};

//реализация подпрограммы вывода элементов массива

void vivod(int n, int a[])

{

     int i;

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

     {

          cout<<setw(5)<<a[i];

     }

     cout<<endl;

};

 

//реализация подпрограммы линейного поиска

void LineSearch(int n, int a[],int b)

{

     int i=0;

     //пока i не превышает размер массива и

     //пока элемент массива не равен ключу

     while ((i<n) && (a[i]!=b))

     {

          i++;      //наращиваем переменную

     }

     if (i==n) cout<<"Ключ не найден"<<endl;

          else if (i<n)

              cout<<"Ключ находится на "<<i+1<<" позиции"<<endl;

     return;  

}

2) с использованием стоппера

 

#include <iostream.h>

#include <iomanip.h>

#include <ctime>

//прототип подпрограммы заполнения массива

void vvod(int n, int a[]);

//прототип подпрограммы вывода элементов массива

void vivod(int n, int a[]);

//прототип подпрограммы линейного поиска

int LineSearch(int n, int a[],int b);

 

int main()

{

     system("chcp 1251>nul");

     int n,*a, i;      

     cout<<"Введите размер массива n=";

     cin>>n;

     //выделяем память под массив для n+1 элемента

     a=new int [n+1];

     vvod(n,a);

     cout<<"Исходный массив:"<<endl;

     vivod(n,a);

     int b;    //ключ

     cout<<"Введите ключ "; cin>>b;

     // n+1 элементом массива становится ключ

     a[n]=b;

     //переменная k будет хранить номер позиции ключа

     int k=LineSearch(n,a,b);

     if (k==n) cout<<"Ключ не найден"<<endl;

          else if (k<n)

              cout<<"Ключ находится на "<<k+1<<" позиции"<<endl;

     //освобождение памяти из массива

     delete[] a;

     system("pause");

     return 0;

}

//реализация подпрограммы заполнения массива

void vvod(int n, int a[])

{

     int a1,b1,i;

     cout<<"Введите диапазон заполнения масссива: ";

     cin>>a1>>b1;

     cout<<"Исходный массив:"<<endl;

     srand(time(NULL));

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

     {

          a[i]=(b1-a1)*rand()/32767+a1;

     }

};

//реализация подпрограммы вывода элементов массива

void vivod(int n, int a[])

{

     int i;

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

     {

          cout<<setw(5)<<a[i];

     }

     cout<<endl;

};

 

//реализация подпрограммы линейного поиска

//подпрограмма возвращает номер позиции ключа

int LineSearch(int n, int a[],int b)

{

     //пока элемент массива не равен ключу

     int i=0;

     while (a[i]!=b)

     {

          i++;      //наращиваем номер массива

     }

     //возвращаем номер позиции ключа

     return i;

}

 

Следует отметить, что в общем случае при линейном поиске среди N элементов требуется в среднем N/2 сравнений в случае успешного поиска и N сравнений в наихудшем случае, и затраты времени для больших массивов поэтому велики.

Применяется данный алгоритм, если никакой дополнительной информации о данных массива нет.

 

3. Бинарный поиск

Очевидно, что нельзя каким-либо способом ускорить поиск, если отсутствует информация о данных, среди которых производится поиск. Также известно, что если данные упорядочены, то поиск можно сделать значительно эффективнее. Поэтому рассмотрим алгоритм, который основан на том, что массив A упорядочен (т.е.  a[i-1]<=a[i] при 1<=i<N).

Смысл метода: берут средний элемент массива и сравнивают его с ключом. В результате возможны 3 случая:

1) если элемент массива равен ключу, то искомый элемент найден;

2) если элемент массива меньше ключа, то все элементы массива с индексами, которые меньше N/2 исключаются из рассмотрения;

3) если элемент массива больше ключа, то все элементы массива с индексами, которые больше N/2 исключаются из рассмотрения;

Затем поиск продолжается в одной из половин массива аналогичным образом.

 

#include <iostream.h>

#include <iomanip.h>

#include <ctime>

//прототип подпрограммы заполнения массива

void vvod(int n, int a[]);

//прототип подпрограммы вывода элементов массива

void vivod(int n, int a[]);

//прототип подпрограммы бинарного поиска

int BinarySearch(int a[], int b, int n);

//прототип подпрограммы сортировки методом прямого включения

void insert(int m[],int n);

 

int main()

{

     system("chcp 1251>nul");

     int n,*a;     

     cout<<"Введите размер массива n=";

     cin>>n;

     a=new int[n];

     cout<<"Начальный массив:"<<endl;

     vvod(n,a);

     vivod(n,a);

     cout<<endl;

     //сортировка

     insert(a,n);

     cout<<"Отсортированный массив:"<<endl;

     vivod(n,a);

 

     int b;    //ключ

     cout<<"Введите ключ "; cin>>b;   

     //переменная k будет хранить номер позиции ключа

     int k=BinarySearch(a, b, n);

     if (k!=-1)         cout<<"Ключ находится на "<<k+1<<" позиции"<<endl;

          else cout<<"Ключ не найден"<<endl;

     //освобождение массива из памяти

     delete[] a;

     system("pause");

     return 0;

};

//реализация подпрограммы заполнения массива

void vvod(int n, int a[])

{

     int a1,b1,i;

     cout<<"Введите диапазон заполнения масссива: ";

     cin>>a1>>b1;

     cout<<"Исходный массив:"<<endl;

     srand(time(NULL));

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

     {

          a[i]=(b1-a1)*rand()/32767+a1;

     }

};

//реализация подпрограммы вывода элементов массива

void vivod(int n, int a[])

{

     int i;

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

     {

          cout<<setw(5)<<a[i];

     }

     cout<<endl;

};

 

//реализация подпрограммы бинарного поиска

//подпрограмма возвращает номер позиции ключа

int BinarySearch(int a[], int b, int n)

{

     //номер среднего элемента

     int m;   

     // левая и правая границы исследуемой части массива

     int left=0, right=n-1;

     // пока левая граница не сравняется с правой

     while (left <= right)

     {

     // находим середину исследуемой части массива

     m = (left + right) / 2;

     //если ключ меньше среднего элемента

     if (b < a[m])            

          // меняем правую границу

          //т.е. отбрасываем правую часть массива из рассмотрения

          right = m - 1;       

          //если ключ больше среднего элемента

          else if (b > a[m])         

              // меняем левую границу

              //т.е. отбрасываем левую часть массива из рассмотрения

              left = m + 1;        

              //если ключ равен среднему элементу

              //заканчиваем выполнение подпрограммы

              //возвращаем номер позиции среднего элемента

              else  return m;

     }

     //если элемент не найден, возвращаем -1

     if (left >= right) return -1;

}

//реализация подпрограммы сортировки методом прямого включения

void insert(int m[],int n)

{

     int tmp;

     int j;

     for(int i=1; i<=n-1; i++)

     {

          tmp=m[i];

          j=i;

           while (j>0 && m[j-1]>tmp)

           {

              m[j]=m[j-1];

          j--;

           }

           m[j]=tmp;

     }   

}

 

Нахождение элемента бинарным поиском осуществляется очень быстро. При поиске среди N элементов требуется log2(N) сравнений в наихудшем случае. Кроме того, бинарный поиск уже при N порядка 100 значительно эффективнее линейного - как по скорости обнаружения, так и по способности к получению отрицательного результата. Для доказательства приведем следующие характеристики линейного и бинарного поиска:

 

 

Линейный поиск

Бинарный поиск

количество элементов

10

10

среднее количество сравнений при наличии элемента

5

 

количество сравнений при отсутствии элемента

10

 

максимальное количество сравнений при наличии элемента

 

8

максимальное количество сравнений при отсутствии элемента

 

8

количество элементов

1000

1000

среднее количество сравнений при наличии элемента

500

 

количество сравнений при отсутствии элемента

1000

 

максимальное количество сравнений при наличии элемента

 

10

максимальное количество сравнений при отсутствии элемента

 

10

количество элементов

1000000

1000000

среднее количество сравнений при наличии элемента

500000

 

количество сравнений при отсутствии элемента

1000000

 

максимальное количество сравнений при наличии элемента

 

20

максимальное количество сравнений при отсутствии элемента

 

20

 

Контрольные вопросы.

1.  Что такое поиск?

2.  Что называется ключом поиска?

3.  Какие известны методы поиска?

4.  Какой алгоритм поиска является наиболее эффективным?

5.  Какое требование предъявляется к структуре данных, в которой выполняется двоичный поиск?

6.  Чем отличается поиск в массиве от поиска в списке?

7.  Чем отличаются процедуры поиска в односвязном и двусвязном списках?

8.  В чем заключается метод линейного поиска?

9.  В чем заключается метод двоичного поиска?

10.  В чем заключается поиск в списке?

11.  Почему двоичный поиск получил такое название?

12.  Пригоден ли двоичный метод для поиска данных в неупорядоченной структуре?

13.  Какой из методов поиска данных в массиве является более универсальным?

14.  Существуют ли какие-нибудь недостатки у линейного поиска? Если да, то какие?