Контрольная работа по "Программированию"

Задание №1

Составить алгоритм в виде блок-схемы, написать и отладить поставленную задачу с использованием рекурсивной и обычной функций. Сравнить полученные результаты.

В упорядоченном массиве целых чисел ai (i = 1, ..., n) найти номер находящегося в массиве элемента c, используя метод двоичного поиска.

Решение:

#include <iostream>

#include <cmath>

#include <cstdlib>

#include <iomanip>

using namespace std;

void PrintArray(int *array, int n) {   // вывод массива

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

        cout << array[i] << " ";       // выводим элементы массива

    cout << endl;

}

// ввод массива с клавиатуры

void ReadArray(int *array, int n) {

    cout << "Enter values of sorted array: ";

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

        cin >> array[i]; // вводим элементы массива

}

// бинарный поиск

int BinarySearchArray(int *array, int n, int value) {

    if (value < array[0] || value > array[n - 1]) // если элемента нет в массиве

        return -1; // возвращаем -1

    //левая и правая граница поиска

    int left = 0;

    int right = n;

    //  индекс элемента посередине

    while (left < right) {

        int mid = left + (right - left) / 2;

        if (value <= array[mid]) { // если искомый элемент меньше или равен центральному

            right = mid; // сдвигаем правую границу

        }

        else { // иначе

            left = mid + 1; // сдвигаем левую границу

        }

    }

    return array[right] == value ? right : -1; // возвращаем индекс элемента, если нашли

}

// рекурсивный бинарный поиск

int BinarySearchRecursiveArray(int *array, int left, int right, int value) {

    if (left >= right)

        return array[right] == value ? right : -1; // возвращаем индекс элемента, если нашли

    int mid = left + (right - left) / 2; // находим индекс посередине

    if (value <= array[mid]) { // если элемент меньше или равен центральному