Разобрать алгоритм

Question

Можете пожалуйста подробно разобрать этот алгоритм и рассказать как он работает, и что он делает?

#include <iostream>
using namespace std;
void input(int*& arr, int size) {
        for (int i = 0; i < size; i++) {
                arr[i] = rand() % 10;
        }
}
        void output(int*& arr, int size) {
        for (int i = 0; i < size; i++) {
                cout << arr[i] << " ";
        }
        cout << endl;
}
int* insertionSort(int arr[], int size) {
        for (int i = 0; i < size - 1; i++) {
                int buf = arr[i];
                for (int j = i + 1; j < size; j++) {
                        if (buf > arr[j]) {
                                arr[i] = arr[j];
                                arr[j] = buf;
                                buf = arr[i];
                        }
                }
        }
        return arr;
}
bool binarySearch(int arr[], int size, int find) {
        int* sortedArr = insertionSort(arr, size);

        int high=size, low=0;
        int middle=(high-low)/2;
        while (low<=high) {
                if (sortedArr[middle] == find) {
                        return true;
                }
                else if (sortedArr[middle] > find) {
                high = middle-1;
                }
                else if (sortedArr[middle] < find) {
                low = middle+1;
                }
                middle = (high + low) / 2;
        }
        return false;
}
int main() {
        //srand(time(NULL));
        int size;
        cin >> size;
        int* arr = new int[size];
        input(arr, size);
        output(arr, size);
        cout << "binarySearch: " << binarySearch(arr, size, 7);
        return 0;
}

Answer 1

Из того что я поняла(я тоже новичок в c++):
Пойдем сверху вниз.
include - подключаем библиотеку для ввода-вывода

using namespace std - Для того чтобы перед каждым cin и cout не вводить std::

Первый void - ввод массива. Подается указатель(?) на массив и размер массива. Через цикл for от 0 элемента массива до последнего элемента задаются значения от 0 до 9 случайно (rand() % 10).

Второй void - вывод массива. Подается указатель(?) на массив и размер массива. Через цикл for от 0 элемента массива до последнего элемента выводятся элементы массива.

int* insertionSort - Функция для сортировки по возрастанию. Подается массив и его размер. Первый цикл идет от 0 элемента массива до предпоследнего. Создается переменная int buf для того, чтобы два числа можно было менять местами. Потом идет еще один цикл внутри предыдущего, он проходит по массиву от 1 элемента до последнего. Т.е. пока у нас i=0 мы проходим j=1..size, потом становится i=1 и мы снова идем j=2..size и так далее. Функция работает так: в переменную buf записываем первый элемент массива. Если buf больше чем следующий элемент, то меняем их местами. Таким образом самый большой элемент окажется в самом конце.

bool binarySearch - поиск элемента в массиве. У нас есть массив, первым же действием сортируется. У нас есть переменные high - номер последнего элемента массива, и low - номер первого, и middle - номер среднего. Дальше цикл - до тех пор, пока low меньше или равно high мы берем элемент под номером middle и смотрим, совпадает ли его значение с тем, что мы ищем. Если да - возвращаем true, функция закончила работу. Если нет, смотрим дальше: если этот элемент больше чем то, что мы ищем, то переменная high принимает значение middle-1, а если он меньше, то low принимает значение middle+1. После этого соответственно меняется значение middle. В конце получится, что или мы найдем нужный элемент, и функция выдаст true, или low станет больше чем high и функция выдаст false, т.е. такого элемента нет. Я думаю, такая функция полезна если у нас большой массив, а при маленьком проще пройтись по всему массиву и найти нужное значение.

int main - основное тело программы. Задается размер, который вводится с клавиатуры. Создается массив такого размера. Заполняется через функцию input(первый void). Выводится через функцию output(второй void). Ищется в массиве элемент со значением 7 и ответ выводится в командную строку.
Вроде все.

БЛОГ НА HUSL

Разобрать алгоритм

Ответы (1 шт):