数据结构的算法复杂度

Question

问题遇到的现象和发生背景

问题相关代码，请勿粘贴截图

C或C++

运行结果及报错内容

按要求复杂度出结果

我的解答思路和尝试过的方法

我已经用python完成了一遍

我想要达到的结果

C或C++顺利运行并达到问题所求

Answer 1

二分查找的时间复杂度是O(logn)，假设学生信息按照学号升序拍好录入，
运行结果：

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#define N 1000
typedef struct _stu
{
    int id; //学号
    char name[20];//姓名
    char sex;//性别
    char pro[20]; //专业
    int grade; //班级
    float score; //绩点
}Student;

typedef struct _node
{
    Student stu[N];
    int nmb; //实际学生数量
}LinkList;

//数组以升序排列时，二分法查找x,返回在顺序表中stu数组中的下标
int binSearch(LinkList *list,int x)
{
    int low, high, mid;
    int n = list->nmb;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (x < list->stu[mid].id)
            high = mid - 1;
        else if (x > list->stu[mid].id)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

//录入数据
void input(LinkList* list)
{
    int i, n;
    printf("请输入学生数量：");
    scanf("%d", &n);
    list->nmb = n;
    for (i = 0; i < n; i++)
    {
        printf("请输入学生%d的学号：",i+1);
        scanf("%d", &list->stu[i].id);
        printf("请输入学生%d的姓名：",i+1);
        scanf("%s", list->stu[i].name);
        getchar(); //吸收回车符
        printf("请输入学生%d的性别：",i+1);
        scanf("%c", &list->stu[i].sex);
        printf("请输入学生%d的专业：",i+1);
        scanf("%s", list->stu[i].pro);
        printf("请输入学生%d的班级：",i+1);
        scanf("%d", &list->stu[i].grade);
        printf("请输入学生%d的绩点：",i+1);
        scanf("%f", &list->stu[i].score);
    }
}

//显示学生信息
void showStu(Student stu)
{
    printf("学号：%d\n", stu.id);
    printf("姓名：%s\n", stu.name);
    printf("性别：%c\n", stu.sex);
    printf("专业：%s\n", stu.pro);
    printf("班级：%d\n", stu.grade);
    printf("绩点：%.2f\n", stu.score);
}

int main()
{
    int i, n;
    int id;
    LinkList list;
    input(&list); //录入数据，按照学号升序排序录入
    printf("请输入要查找的学号：");
    scanf("%d", &id);
    n = binSearch(&list,id );
    if (n == -1)
        printf("查无此人！\n");
    else
        showStu(list.stu[n]);
    return 0;
}