#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

int search(int *arr, int size, int k);
int fibonacci(int *arr, int size, int k);
void generate(int *arr, int size);
void writeToFile(int *arr, int size);
int *readFromFile(int size);
//int partition(int *arr, int low, int high);
//void quickSort(int *arr, int low, int high);

int main() 
{
 setlocale (LC_ALL, "UKR");
 system ("chcp 1251");
 
 int size;
 printf("Введіть розмір масиву: ");
 scanf("%d", &size);

    if (size < 1000) 
    {
        printf("Розмір масиву повинен бути більше 1000. Програма завершується.\n");
        return 0;
    }
 
 int *arr = (int *)malloc(size * sizeof(int));
 if (arr == NULL) 
    {
        printf("Помилка виділення пам'яті.\n");
        return 0;
    }
 generate(arr, size); 
 writeToFile(arr, size);
 printf("Масив записано у файл.\n");
 
 arr = readFromFile(size);
    if (arr == NULL) 
    {
        printf("Програма не виконана.\n");
        return 0;
    }
//    quickSort(arr, 0, size-1);
    printf("Програма працює успішно.\n");
 
 
 int k;
 printf("Введіть значення, яке потрібно знайти: ");
 scanf("%d", &k);

// Пошук за допомогою послідовного пошуку
 int sIndex = search(arr, size, k);
 if (sIndex != -1) 
    {
        printf("Елемент знайдено за послідовним пошуком під порядковим номером: %d\n", sIndex);
    } 
 else 
    {
        printf("Елемент не знайдено за послідовним пошуком.\n");
    }
    
// Пошук за допомогою методу Фібоначчі
 int fIndex = fibonacci(arr, size, k);
 if (fIndex != -1) 
    {
        printf("Елемент знайдено за методом Фібоначчі під порядковим номером: %d\n", fIndex);
    } 
 else 
    {
        printf("Елемент не знайдено за методом Фібоначчі.\n");
    }

 free(arr);

 return 0;
}


int search(int *arr, int size, int k) 
{
    int i;
    for (i=0; i<size; i++) 
    {
        if (arr[i] == k) 
        {
            return i;
        }
    }
    return -1;  
}

int fibonacci(int *arr, int size, int k) 
{
    if (arr == NULL || size == 0) 
    {
        return -1;
    }
    
    if (k < arr[0] || k > arr[size - 1]) 
    {
        return -1;
    }
    
    
    int fib2 = 0; // попереднє число Фiбoначчi
    int fib1 = 1; // поточне число Фiбoначчi
    int temp; 

    while (fib1 < size-1) 
    {
        temp = fib1;
        fib1 = fib1 + fib2;
        fib2 = temp;
    }
    
    int left_index = 0; 
    int mid_index = fib1 - 2;
    while (fib1 > 1) 
    {
        if (mid_index >= size-1) 
        {
            mid_index = size - 1;
        }
        switch (k - arr[mid_index]) 
        {
            case 0:
                return mid_index;
                
            case -1:
                mid_index = mid_index - (fib1 - fib2 - 1);
                temp = fib1;
                fib1 = fib1 - fib2;
                fib2 = temp - fib1;
                break;
                
            case 1:
              
                left_index = mid_index + 1;
                temp = fib1;
                fib1 = fib2;
                fib2 = temp - fib1;
                break;
        }
    }
        if (fib1 == 1 && arr[left_index] == k) 
            return left_index;
            
        return -1;
}

void generate(int *arr, int size) 
{
    int i;
    srand(time(NULL));
    
    for (i=0; i<size; i++) 
    {
        arr[i] = rand() % size + 1;
    }
}

void writeToFile(int *arr, int size) 
{
    FILE *file = fopen("array.txt", "w");
    if (file == NULL) 
    {
        printf("Помилка відкриття файлу для запису.\n");
        return;
    }

    int i;
    for (i=0; i<size; i++) 
    {
        fprintf(file, "%d\n", arr[i]);
    }
    fclose(file);
}

int *readFromFile(int size) 
{
    FILE *file = fopen("array.txt", "r");
    if (file == NULL) 
    {
        printf("Помилка відкриття файлу для читання.\n");
        return NULL;
    }

    int *arr = (int *)malloc(size * sizeof(int));
    if (arr == NULL) 
    {
        printf("Помилка виділення пам'яті.\n");
        fclose(file);
        return NULL;
    }

    int i;
    for (i=0; i<size; i++) 
    {
        if (fscanf(file, "%d", &arr[i]) != 1) 
        {
            printf("Помилка читання з файлу.\n");
            free(arr);
            fclose(file);
            return NULL;
        }
    }
    fclose(file);
    return arr;
}

/*int partition(int *arr, int low, int high) 
{
    int pivot=arr[high];  
    int i = low - 1;
    int j = high + 1;
    int temp;
    
    if (low >= high) 
    {  return high;  }
    
    while (1) 
    {
        do 
        {
            i++;
        } while (arr[i] < pivot);

        do 
        {
            j--;
        } while (arr[j] > pivot);

        if (i >= j)
            return j;

        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

void quickSort(int *arr, int low, int high) 
{
    int stack[high - low + 1]; 
    int top = -1;

    stack[++top] = low;
    stack[++top] = high;

    while (top >= 0) 
    {
        high = stack[top--];
        low = stack[top--];

        int pi = partition(arr, low, high);
        if (pi - 1 > low) 
        {
            stack[++top] = low;
            stack[++top] = pi - 1;
        }
        
        if (pi + 1 < high) 
        {
            stack[++top] = pi + 1;
            stack[++top] = high;
        }
    }
}*/