Algorithms lab 1 version 1.0

#define CRT_SECURE_NO_WARNINGS
#include "pch.h"
#include <iostream>
#include <limits.h>

using namespace std;

struct Result *s_search(int arr[], int K);
struct Result *q_search(int arr[], int K);
struct Result *t_search(int arr[], int K);
struct Result *bin_search(int arr[], int N, int K);
void sort(int arr[]);
void initialize_result(struct Result *result);

struct Result
{
    int count = 0;
    int index[21];
    int oper_count[21];
};

int main()
{
    int i;
    int N = 21;
    int arr[] = { 23, 74, 52, 11, 23, 9, 67, 48, 12, 23, 64, 73, 6, 29, 97, 34, 76, 23, 15, 49, 5 };
    int K;
    K = 23;
    struct Result result;

    result = *s_search(arr, K);
    if (result.count > 0)
    {
        for (i = 0; i <= result.count; i++)
        {
            printf("Algorithm S: found at position %d, %d operations were required.\n", result.index[i], result.oper_count[i]);
        }
    }
    else
    {
        printf("Algorithm S: not found, %d operations were required.\n", result.oper_count[0]);
    }

    result = *q_search(arr, K);
    if (result.count >= 0)
    {
        for (i = 0; i <= result.count; i++)
        {
            printf("Algorithm Q: found at position %d, %d operations were required.\n", result.index[i], result.oper_count[i]);
        }
    }
    else
    {
        printf("Algorithm Q: not found, %d operations were required.\n", result.oper_count[0]);
    }

    sort(arr);
    printf("Array was sorted.\n");

    result = *t_search(arr, K);
    if (result.count > 0)
    {
        for (i = 0; i <= result.count; i++)
        {
            printf("Algorithm T: found at position %d, %d operations were required.\n", result.index[i], result.oper_count[i]);
        }
    }
    else
    {
        printf("Algorithm T: not found, %d operations were required.\n", result.oper_count[0]);
    }

    result = *bin_search(arr, N, K);

    if (result.count >= 0)
    {
        for (i = 0; i <= result.count; i++)
        {
            printf("Algorithm B: found at position %d, %d operations were required.\n", result.index[i], result.oper_count[i]);
        }
    }
    else
    {
        printf("Algorithm B: not found, %d operations were required.\n", result.oper_count[0]);
    }
}

struct Result *s_search(int arr[], int K)
{
    struct Result result;
    int i;
    int oper_count = 0;
    initialize_result(&result);
    for (i = 0; i < 21; i++)
    {
        oper_count += 2; //Проверка условия и увеличение i
        if (arr[i] == K)
        {
            oper_count++; //Проверка условия
            result.count++;
            result.oper_count[result.count] = oper_count;
            result.index[result.count] = i;
        }
    }
    if (result.count < 0) //Если не найдено
    {
        result.oper_count[0] = oper_count;
    }
    return &result;

}
struct Result * q_search(int arr[], int K)
{
    int i;
    int oper_count = 0;
    struct Result result;
    initialize_result(&result);

    int farr[22]; //Фиктивный массив
    for (i = 0; i < 21; i++) //Добавление фиктивной записи
    {
        farr[i] = arr[i];
    }
    farr[21] = K;
    i = 0;
    while (1)
    {
        if (farr[i] == K)
        {
        oper_count++; //Проверка
            if (i <= 20)
            {
                oper_count++; //Проверка
                result.count++;
                result.oper_count[result.count] = oper_count;
                result.index[result.count] = i;
            }
            else
            {
                if (result.count < 0) //Если не найдено
                {
                    result.oper_count[0] = oper_count;
                }
                return &result; //Пройдены все элементы массива
            }
        }
        i++;
        oper_count++; //Увеличение i
    }
}

struct Result *t_search(int arr[], int K)
{
    struct Result result;
    int oper_count = 0;
    int i;
    initialize_result(&result);
    result.count = -1;
    result.oper_count[result.count] = 0;
    int farr[22]; //Фиктивный массив
    for (i = 0; i < 21; i++) //Добавление фиктивной записи
    {
        farr[i] = arr[i];
    }
    farr[21] = INT_MIN;
    i = 0;
    while (1)
    {
        //TODO: посмтореть, что с числом операций, оно странно подсчитывается
        if (K >= farr[i])
        oper_count++; //Проверка
        {
            if (K == farr[i]){
                oper_count++; //Проверка
                result.count++;
                result.oper_count[result.count] = oper_count;
                result.index[result.count] = i;
            }
            //Нужно какое-то условие выхода из цикла. Оно замедлит алгоритм, т.к. оно в цикле.
            //TODO: подумать, что с этим можно сделать
            if (i == 22)
            {
                oper_count++; //Проверка
                break;
            }
        }
        i++;
        oper_count++; //Увеличение i
    }
    if (result.count < 0) //Если не найдено
    {
        result.oper_count[0] = oper_count;
    }
    return &result;
}

struct Result *bin_search(int arr[], int N, int K)
{
    int first_upper_index = -1;
    int first_left_index = -1;
    int oper_count;
    int flag = 0; //0 - не найдено, 1 - найдено
    int mid, left = 0, right = N - 1;
    struct Result result;
    initialize_result(&result);

    oper_count = 0;

    //Поиск самого левого подходящего элемента
    while (left <= right)
    {
        oper_count++; //Проверка условия цикла
        mid = (left + right) / 2;
        oper_count++; //Операция присваивания
        if (K >= arr[mid])
        {
            right = mid - 1;
            oper_count += 2; //Проверка условия и операция присваивания
        }
        else //K < arr[mid]
        {
            left = mid + 1;
            oper_count += 2; //Проверка условия и операция присваивания
        }
    }
    first_left_index = mid;
    result.count = 0;
    result.oper_count[0] = oper_count;
    result.index[0] = first_left_index;
    if (first_left_index < 0) //Если не найдено
    {
        result.count = -1;
        return &result;
    }

    //Поиск первого неподходящего элемента справа
    left = 0;
    right = N - 1;

    while (left <= right)
    {
        oper_count++; //Проверка условия цикла
        mid = (left + right) / 2;
        oper_count++; //Операция присваивания
        if (K <= arr[mid])
        {
            left = mid + 1;
            oper_count += 2; //Проверка условия и операция присваивания
        }
        else //K > arr[mid]
        {
            right = mid - 1;
            oper_count += 2; //Проверка условия и операция присваивания
        }
    }
    first_upper_index = left; //TODO: понять, почему left, а не mid


    result.count = (first_upper_index - first_left_index - 1);
    for (int i = 1; i <= result.count; i++)
    {
        result.index[i] = first_left_index + i;
        result.oper_count[i] = oper_count + i; //Операция присваивания
    }
    return &result;
}

void sort(int arr[]) //Сортировка по убыванию пузырьком
{
    int i, j, temp;
    for (i = 0; i < 21; i++)
    {
        for (j = i; j < 21; j++)
        {
            if (arr[i] < arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

void initialize_result(struct Result *result)
{
    int i;
    result->count = -1;
    for (i = 0; i < 21; i++)
    {
        result->index[i] = 0;
        result->oper_count[i] = 0;
    }
}