Программы по двоичному поиску

Размещено на http://www.allbest.ru/

Реферат

бинарный алгоритм поиск

Пояснительная записка 13 с., 1 рис., 3 источника.

ПОИСК, ПРОГРАММА, АЛГОРИТМ, ФАЙЛ, ФУНКЦИЯ, СОРТИРОВКА, МАССИВ, ЦИКЛ, КЛЮЧ, ЭЛЕМЕНТ

Объектом работы является задача по написанию программы по двоичному поиску.

Цель работы - определение оптимального алгоритма.

Методом сравнительного анализа выбран алгоритм деления массива на две части.

В результате разработки программы подтвердилась правильность выбора алгоритма.

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



Содержание

Введение

1. Описание алгоритма

2. Разработанная программа

3. Результаты выполнения программы

Заключение

Список литературных источников



Введение

Первоначально применение ЭВМ ограничивалось в основном вычислительными задачами, и структуры данных были очень простыми - числа и числовые массивы. Основную трудность в создании программ представляло проектирование алгоритма.

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

Проектирование структуры данных является наиболее трудной и ответственной проблемой в создании сложных программ. Выбор структуры данных и способа их представления в памяти компьютера во многом (иногда почти однозначно) определяет структуру алгоритма [1].

Одно из наиболее часто встречающихся в программировании действий - поиск данных. Существует несколько основных вариантов поиска, и для них создано много различных алгоритмов. Поиск требуемой информации применяется ко всем основным структурам данных с произвольным доступом: массивам, спискам (одно- и двусвязным), деревьям, графам, таблицам. На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых -- метод бинарного поиска.

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

Самое широкое распространение метод получил в информатике для навигации (поиска) в структурах данных. Также его применяют в качестве численного метода для нахождения приближённого решения уравнений. Метод служит для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до можно за время, где. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт времени [2].



1. Описание алгоритма

Предположим, что мы обратились к середине файла и обнаружили там ключ К_i. Сравним К и К_i. Если К = К_i, то нужная запись найдена. Если K < К_i, то ключ К должен находиться в части файла, предшествующей К_i (если запись с ключом К вообще существует). Аналогично, если К_i < К, то дальнейший поиск следует вести в части файла, следующей за К_i. Если повторять эту процедуру проверки ключа К, из середины не просмотренной части файла, тогда каждое безуспешное сравнение К с К_i будет исключать из рассмотрения приблизительно половину не просмотренной части.

Algorithm BSEARCH (Binary search - двоичный поиск) поиска записи с ключом К в файле с N ? 2 записями, ключи которых упорядочены по возрастанию K₁ < K₂ ... < K_N.

Шаг 0. [Инициализация] Set FIRST< 1; LAST< N. (FIRST и LAST- указатели первого и последнего ключей в еще не просмотренной части файла.)

Шаг 1. [Основной цикл] While LAST ? FIRST do through шаг 4 od.

Шаг 2. [Получение центрального ключа] Set I< |_(FIRST + LAST)/2_| .(K_i ключ, расположенный в середине или слева от середины еще не просмотренной части файла.)

Шаг 3. [Проверка на успешное завершение] If K=Ki then PRINT «Успешное окончание, ключ равен К_I»; and STOP fi.

Шаг 4. [Сравнение] If K < K_I then set LAST< I-1 else set FIRST<I+1 fi.

Шаг 5. [Безуспешный поиск] PRINT «безуспешно»; and STOP [3].



2. Разработанная программа

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <cstdio>

using namespace std;

void newMas(int *mas,int &size);// заполнение массива и его сортировка

void file(int *mas,int &size); // открытие (создание нового) файла и запись массива в файл

int search(int *mas,int &size,int key);// загрузка массива из файла и поиск числа

int main() {

setlocale(LC_ALL, "rus"); // корректное отображение Кириллицы

int S,K;//количетсво элементов в массиве и искомое значение (ключ)

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

cin >> S; // ввод размера массива

int *M = new int[S]; // Выделение памяти для массива

newMas(M,S);

file(M,S);

cout<<"Введите число для поиска: "<<endl;

cin>>K;

if(search(M,S,K) < 0)

cout<<"Число "<< K <<" в прочтенном файле не обнаружено"<<endl;

else

cout<<"Число "<< K <<" расположено в позиции:" << search(M,S,K) << endl;

delete [] M; // очистка памяти

system("pause");

return 0;

}

void newMas(int *mas,int &size){

cout<<"Заполнение массива:"<<endl;

cout<<"Вводите числа через ENTER: "<<endl;

for (int i = 0; i < size; i++) { // Заполнение массива числами

cin>>mas[i];}

sort(mas, mas+size);// сортировка массива стадатной фунцией

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

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

cout<<mas[i]<<endl;//вывод отсортированного массива

}

void file(int *mas,int &size){

FILE *file;

if ((file = fopen("file.txt", "wb")) != NULL) // открытие файладля записи массива

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

fprintf(file, "%d", mas[i]);//запсись массива в файл

fclose(file);// закрытие файла

}

int search(int *mas,int &size, int key)

{

FILE *file;

if ((file = fopen("file.txt", "rb"))!=NULL)// открытие файладля чтения массива

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

fscanf(file, "%d", &mas[i]);//чтение массива из файла в программу

fclose(file);

int left, right, mid;//объявление переменных-границ и среднего элемента

left = 0;

right = size;

while(left <= right) {// проверка условия выполнения цикла

mid = (left + right) / 2;//определение середины массива

if(key < mas[mid])

right = mid - 1;//"откидывание" правой части массива и уменьшение диапазона левой части

else if(key > mas[mid])

left = mid + 1;//"откидывание" левой части массива и уменьшение диапазона правой части

else

return mid;// возврат номера элемента в главную функцию

}

return -1;// возврат отрицательного значения (поиск не дал результатов)

}

3. Результаты выполнения программы

Введите размер массива: 27

Заполнение массива:

Вводите числа через ENTER:

6

546

29

-816

543

687

549

-38

-86

-516

84

38

189

84

4

1

168

-86

86

16

-819

-89

-889

-847

846

647

58

Отсортированный массив:

-889

-847

-819

-816

-516

-89

-86

-86

-38

1

4

6

16

29

38

58

84

84

86

168

189

543

546

549

647

687

846

Введите число для поиска:

-516

Число -516 расположено в позиции: 4

Для продолжения нажмите любую клавишу . . .



Заключение

Бинарный (двоичный, дихотомический) поиск является поиском заданного элемента на упорядоченном множестве, осуществляемым путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Бинарный поиск применяется к отсортированным множествам.

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



Список литературных источников

1.Казанский национальный исследовательский технический университет им. А. Н. Туполева. Программирование(4172,4173). Лекции. Лекция 14. Данные и алгоритмы // http://www.studfiles.ru/preview/2020438/

2.Левитин А. В. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы. Введение в разработку и анализ -- М.: Вильямс, 2006. -- С. 180--183. -- 576 с. -- ISBN 978-5-8459-0987-9

3.Предместьин В. Р., Моисеева И. Д., Семенова М. Э. Курсовая работа по программированию и основам алгоритмизации. Методические указания / ГОУ ВПО «РХТУ им. Д. И. Менделеева», Новомосковский институт (филиал). - Новомосковск, 2009 - 44с.

Размещено на Allbest.ru

...