7. Алгоритмы поиска и сортировки.

7.1. Последовательный поиск в неупорядоченном массиве.

Дано :

A[n]- массив целых чисел,

х -вещественное число.

Определить, есть ли в вещественном массиве А элемент, совпадающий с заданным значением х.

Выполняем последовательное сравнение элементов массива А с заданным значением x до тех пор, пока либо элемент массива совпадет с x, либо пройдем весь массив и поиск закончится безуспешно.

Вариант 1.(Используем цикл с параметром for)

include <iostream.h>

#include <conio.h>

const int n=15;

void main(){

int A[n],x, i;

clrscr();

cout<<"\n введите "<<n<<" элементов\n";

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

cin>>A[i];

cout<<"\n введите x\n";

cin>>x;

for (i=0; i<n&&A[i]!=x;i++);

if(i==n) cout<<”\n нет такого в массиве\n”;

else

cout<<”\n номер первого элемента, совпадающего с заданным ”<<i;

getch();}

7.2 Последовательный поиск c барьером.

В предыдущей программе используется алгоритм линейного поиска в массиве. Инварианта цикла содержит два условия. Упростим инварианту цикла. При этом существенно сократится количество операций(n операций сравнения в случае неудачного поиска). Предлагается алгоритм “поиск с барьером”.

Добавим в массив один элемент – барьер (A_n), и перед началом поиска поместим Х в "барьер". При этом отпадает необходимость использовать в заголовке цикла условие (i<n).

Вариант 1.(Используем цикл с параметром for)

include <iostream.h>

#include <conio.h>

const int n=15;

void main(){

int A[n+1],x, i;

clrscr();

cout<<"\n введите "<<n<<" элементов\n";

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

cin>>A[i];

cout<<"\n введите x\n"; cin>>x;

A[n]=x; // барьер

for (i=0;A[i]!=x;i++);

if(i==n) cout<<”\n нет такого в массиве\n”;

else

cout<<”\n номер первого элемента, совпадающего с заданным ”<<i; getch();}

7.3 Дихотомический поиск в упорядоченом массиве.

Определить, найдется ли в заданном упорядоченном целочисленном массиве элемент, равный заданному числу Х. Пусть массив упорядочен по возрастанию.

Можно при этом использовать любой из вышеописаных алгоритмов.

Однако предложим более эффективный алгоритм поиска. Используем алгоритм двоичного поиска. Суть его в следующем:

1)пусть L, R –левый и правый концы секции массива , где еще может быть обнаружен Х.Для начала – L=0, R=n-1

2) определить индекс серединного элемента m ( m=(L+R) / 2)

3) Если х>a[m], то поиск сузить до правого интервала(L=m+1),

иначе - до левого(R=m).

4)если L<=R перейти к пункту 2.

include <iostream.h>

#include <conio.h>

const int n=15;

void main(){

int A[n],x;

int i,m,L,R,F=1;

clrscr();

cout<<"\n введите "<<n<<" элементов\n";

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

cin>>A[i];

cout<<”\n введите искомое число x \n”;

cin>>x;

L=0;

R=n-1; {заданы левый и правый концы интервала поиска}

while (L<=R&&F)

{

m=(L+R) / 2;

if (x>a[m]) L=m+1; //сузить поиск до правого интервала

else

if (x<a[m]) R=m; //сузить поиск до левого

else F=0; //нашли

}

if(F) cout<<”\n нет такого в массиве\n”;

else

cout<<”\n номер первого элемента, совпадающего с заданным ”<<m;

}