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

#define N 105

int main() {
    //将时间作为随机数种子
    srand((unsigned int)time(NULL));

    int arr[N];
    int n, max = -1e6, max_p, min = 1e6, min_p;
    double sum, ave;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        arr[i] = rand() % 100 + 1; //产生1-100的随机数
        sum += arr[i];
        //生成时就获得最大值最小值的下标
        if (arr[i] > max) {
            max_p = i;
            max = arr[i];
        }
        if (arr[i] < min) {
            min_p = i;
            min = arr[i];
        }
    }
    //输出原数组
    printf("生成的数组为：\n");
    for (int i = 1; i <= n; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");


    //（1）求出所有高于平均数的数据:
    ave = sum / n;
    printf("所有高于平均数的数据:\n");
    for (int i = 1; i <= n; i++) {
        if (arr[i] > ave)
            printf("%d  ", arr[i]);
    }
    printf("\n");


    //（2）交换最大数和最小数的位置。
    int t = arr[max_p];
    arr[max_p] = arr[min_p];
    arr[min_p] = t;
    printf("交换最大数和最小数的位置后：\n");
    for (int i = 1; i <= n; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");


    //（3）对这组数据进行逆置:
    int t3 = 0;
    for (int i = 1; i <= n / 2; i++) {
        t3 = arr[i];
        arr[i] = arr[n + 1 - i];
        arr[n + 1 - i] = t3;
    }
    printf("对这组数据进行逆置后:\n");
    for (int i = 1; i <= n; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");


    //(4)对这组数进行排序：
    //排序前复制一个数组，以便进行第五小题的顺序查找：
    int arr_c[N];
    for (int i = 1; i <= n; i++) {
        arr_c[i] = arr[i];
    }

    int t4 = 0;
    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (arr[j] > arr[j + 1]) {
                t = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = t;
            }
        }
    }
    printf("对这组数据进行排序后:\n");
    for (int i = 1; i <= n; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");

    //（5）从键盘输入一个数，查找数组中是否存在，并显示其下标:
    int t5;
    printf("请输入一个要查找的数：\n");
    scanf("%d", &t5);
    //5.1对排序前（无序）数据采用顺序查找，显示依次比较的数据、比较次数以及查找结果。
    printf("顺寻查找：\n");
    int flag = 0, id;
    for (int i = 1; i <= n; i++) {
        printf("查找中：%d\n", arr_c[i]);
        if (t5 == arr_c[i]) {
            flag = 1;
            id = i;
            break;
        }
    }

    if (flag == 1)
        printf("目标数字%d存在，下标为：%d,查找次数：%d\n", t5, id, id);
    else
        printf("目标数字%d不存在,查找次数：%d\n", t5, n);
    //5.2对排序后数据采用二分查找，显示依次比较的数据、比较次数以及查找结果。
    printf("二分查找：\n");
    int low = 1, high = n; // 待查区域的边界
    int mid;
    int count = 0;
    flag = 0;
    while (low <= high) {
        count++;
        mid = (high + low) / 2;
        if (arr[mid] == t5) {
            printf("查找中：%d\n", arr[mid]);
            flag = 1;
            break;
        } else if (arr[mid] > t5) {
            printf("查找中：%d\n", arr[mid]);
            high = mid - 1;
        } else if (arr[mid] < t5) {
            printf("查找中：%d\n", arr[mid]);
            low = mid + 1;
        }
    }
    if (flag == 1)
        printf("目标数字%d存在，下标为：%d,查找次数：%d\n", t5, mid, count);
    else
        printf("目标数字%d不存在,查找次数：%d\n", t5, count);

}