/*
codeby.net
Autor: DarkKnight125 (Denis Goncharov)
*/
#include <iostream>
#include <time.h>
using namespace std;
//Функция для переставления местами переменных (для сортировки использовал)
void SwapVal (int &a, int &b)
{
int Temp = a;
a = b;
b = Temp;
}
//Основная функция программы (точка входа)
void main(void)
{
setlocale(LC_ALL,".1251"); //Подгрузка локали
srand(NULL); //Инициализация таймера случ. величины
int Arr[100000]; //Массив на 100,000 элементов
int lIndex = -1; //Индекс элемента (требуемого найти)
int SerchElem; //Его значение
//Генерация массива
cout << "Генерация массива случ. величинами ..." << endl;
for(int i = 0; i < 100000; i++)
{
Arr[i] = rand()%1000000 * (rand()%2?1:-1);
}
cout<< "Сгенерирован массив из 100,000 элементов в диапозоне [-999999, 999999]" <<endl;
cout<< "Введите элемент для поиска : ";
cin >> SerchElem;
time_t pStart = clock(); //Сделаем засечку
//Линейный поиск (методом перебора)
for (int i = 0; i< 100000; i++)
if (Arr[i] == SerchElem)
lIndex = i;
if (lIndex > -1)
cout << "Элемент найден, позиция элемента = " << lIndex << endl;
else cout << "Элемент не найден" << endl;
cout << "Время поиска линейным перебором : "<< (double)(clock()-pStart)/1000 << " мсек"<< endl;
//Отсортировать массив по возрастанию (методом улучшенного пузырька)
cout<< endl << "Выполняется сортировка ..." << endl;
pStart = clock(); //Сделаем временную засечку для сортировки
bool MustSort = true;
for (int i = 0; i < 100000 && MustSort; i++)
{
MustSort = false;
for (int j = 0; j < 100000 - 1 - i; j++)
if (Arr[j] > Arr[j+1])
{
SwapVal(Arr[j],Arr[j+1]);
MustSort = true;
}
}
cout << "Сортировка выполнена, время выполнения : "<< (double)(clock()-pStart)/1000 << " мсек" << endl;
//Поиск Дроичный (Бинарный)
cout << endl << "Выполнение двоичного(бинарного) поиска ..." << endl;
pStart = clock(); //Сделаем временную засечку
int bFirst = 0; //Начальный индекс массива (отсортированного)
int bEnd = 100000 - 1; //Конечный индекс массива (отсортированного)
int bMiddle; //Переменная середины массива
lIndex = -1;
if (SerchElem < Arr[bFirst] || SerchElem > Arr[bEnd])
cout << "Элемент поиска лежит вне массива" << endl;
while ( bFirst < bEnd) //Пока вычисляемые индексы Начала меньше выч. индекса Конца
{
bMiddle = (bFirst + bEnd) / 2; //Найдем индекс середины
if (SerchElem <= Arr[bMiddle]) //Если элемент поиска <= значение массива при срединном индексе
bEnd = bMiddle; //Сместим тогда конец в середину, ведь наш элемент лежит от нач. до средины, или же в аккурат середины
else //Иначе лежит в пределеот (средина, конец]
bFirst = bMiddle + 1;
}
if (Arr[bEnd] == SerchElem) //Если индекс конца указывает на эл. поиска
cout << "Элемент найден, позиция элемента = " << bEnd << endl;
else cout << "Элемент не найден" << endl;
cout << "Время поиска двоичным перебором : "<< (double)(clock()-pStart)/1000 << " мсек"<< endl;
}
