Проектирование структуры данных, определение структуры алгоритма. Понятие бинарного поиска, его распространение и преимущества. Инициализация, основной цикл, получение центрального ключа, проверка на успешное завершение, сравнение, безуспешный поиск.
Аннотация к работе
ПОИСК, ПРОГРАММА, АЛГОРИТМ, ФАЙЛ, ФУНКЦИЯ, СОРТИРОВКА, МАССИВ, ЦИКЛ, КЛЮЧ, ЭЛЕМЕНТ В результате разработки программы подтвердилась правильность выбора алгоритма.Первоначально применение ЭВМ ограничивалось в основном вычислительными задачами, и структуры данных были очень простыми - числа и числовые массивы. В дальнейшем, сначала при разработке трансляторов и операционных систем, а затем и при создании прикладных программ, особенно систем с элементами искусственного интеллекта, экспертных систем, использовались все более сложные структуры данных и центр тяжести в разработке программ перемещался к данным. Поиск требуемой информации применяется ко всем основным структурам данных с произвольным доступом: массивам, спискам (одно-и двусвязным), деревьям, графам, таблицам. На практике довольно часто производится поиск в массиве, элементы которого упорядочены по некоторому критерию (такие массивы называются упорядоченными). В случае, если массив упорядочен, то применяют другие, более эффективные по сравнению с методом простого перебора алгоритмы, один из которых - метод бинарного поиска.Предположим, что мы обратились к середине файла и обнаружили там ключ Кі. Если K <Ki, то ключ К должен находиться в части файла, предшествующей Кі (если запись с ключом К вообще существует). Если повторять эту процедуру проверки ключа К, из середины не просмотренной части файла, тогда каждое безуспешное сравнение К с Кі будет исключать из рассмотрения приблизительно половину не просмотренной части. Algorithm BSEARCH (Binary search - двоичный поиск) поиска записи с ключом К в файле с N ? 2 записями, ключи которых упорядочены по возрастанию K1 <K2 ... [Получение центрального ключа] Set I< |_(FIRST LAST)/2_| .(Ki ключ, расположенный в середине или слева от середины еще не просмотренной части файла.)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 << "Введите размер масива: "; } void NEWMAS(int *mas,int &size){ cout<<"Заполнение массива:"<<endl; } void file(int *mas,int &size){ if ((file = fopen("file.txt", "wb")) != NULL) // открытие файладля записи массива for(int i=0;i<size;i ) fprintf(file, "%d", mas[i]);//запсись массива в файл fclose(file);// закрытие файла if ((file = fopen("file.txt", "rb"))!=NULL)// открытие файладля чтения массива for(int i=0;i<size;i ) fscanf(file, "%d", &mas[i]);//чтение массива из файла в программу fclose(file);Введите размер массива: 27 Заполнение массива: Вводите числа через ENTER: 6Бинарный (двоичный, дихотомический) поиск является поиском заданного элемента на упорядоченном множестве, осуществляемым путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей.