//Бинарный поиск
#include <bios.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <fstream.h>
#include <io.h>
void GetArray(int *mas, int &cnt) //функция загрузки массива из файла
{
cnt=0;
int v;
char *fn="";
cout<<"Введите имя файла с массивом чисел: ";
cin>>fn;
if (access(fn, 0)!=0) //проверим наличие файла
{
cout<<"\nОшибка: Не удается открыть файл!!!\n";
bioskey(0);
exit(1);
}
cout<<"\nЗагрузка массива:\n";
ifstream fin(fn);
while (!fin.eof()) //загрузим все элементы из файла и определим их количество
{
fin>>v;
if (!fin.eof())
{
cnt++;
mas[cnt]=v;
cout<<" "<<v;
}
}
cout<<"\nЗагружено "<<cnt<<" элементов массива.\n";
fin.close();
}
void ShowArray(int *mas, int cnt) //функция вывода массива на экран
{
cout<<"[";
for (int i=1; i<=cnt; i++) {printf("%3d ", mas[i]);}
cout<<"]\n";
}
void SortArray(int *mas, int cnt) //функция сортировки массива (методом выбора)
{
int tmp;
int min=1;
for (int i=1; i<cnt; i++)
{
min=i;
for (int j=i; j<=cnt; j++)
{
if (mas[j]<mas[min]) {min=j;}
}
tmp=mas[min];
mas[min]=mas[i];
mas[i]=tmp;
}
}
int FindValue(int *mas, int cnt, int value, int &step) //рекурсивная функция для поиска элемента в массиве
{
step++;
cout<<"Итерация № "<<step<<", массив для поиска: ";
ShowArray(mas, cnt);
int res;
int mid=(cnt/2)+(cnt%2); //определим середину массива
if (value==mas[mid]) //если элемент оказался в середине, то нашли!
{
cout<<" "<<value<<"=="<<mas[mid]<<"\n\n";
return mid;
}
if (cnt<=1) {return -1;}
if (value<mas[mid]) //если значение меньше среднего элемента массива, то ищем в левой части
{
cout<<" "<<value<<"<"<<mas[mid]<<"\n\n";
res=FindValue(&mas[0], (mid-1), value, step);
if (res<0) {return -1;}
return res;
}
else //если же значение больше среднего элемента массива, то ищем в правой части
{
cout<<" "<<value<<">"<<mas[mid]<<"\n\n";
res=FindValue(&mas[mid], (cnt-mid), value, step);
if (res<0) {return -1;}
return mid+res;
}
}
void main()
{
int N; //количество элементов в массиве
int A[256]; //массив
clrscr();
cout<<"\n < < < Б и н а р н ы й п о и с к > > >\n\n";
GetArray(A, N); //загрузи массив
printf("\nЗагружен следующий массив A[%d]:\n", N);
ShowArray(A, N);
printf("\nПроведем сортировку массива:\n");
SortArray(A, N); //отсортируем массив для поиска
int v; //искомое значение
int i; //позиция найденного элемента в массиве
char ch;
do {
int j=0; //количество итераций
printf("Итоговый массив:\n");
ShowArray(A, N);
printf("\nНайти элемент массива v=");
cin>>v;
printf("\nНачинаем бинарный поиск.\n");
i=FindValue(A, N, v, j);
if (i<=0) {printf("\nЭлемент %d в массиве не найден!\n", v);}
else {printf("\nЭлемент %d найден в %d-й позиции на %d-й итерации.\n", v, i, j);}
printf("\nИскать другой элемент? (ENTER - да)\n\n");
ch=bioskey(0);
clrscr();
} while (ch==13);
} |
