C语言二分查找学生排名程序返回异常值问题求助

问题描述 #

我要编写一个C程序，输入共4行：前三行格式为「姓名#分数」，第四行为待查找的学生姓名，程序需返回该学生的排名（按分数降序排序后的位置）。我将输入数据存入结构体并按分数降序排序，但二分查找部分总是返回不符合预期的值，恳请帮忙解决。

原代码 #

#include <stdio.h>
#include <string.h>

typedef struct {
    char name[11];
    int score;
} report;

int main() {
    int n = 3;
    report student[n];
    for (int i = 0; i < 3; i++) {
        scanf("%[^\#]#%d", student[i].name, &student[i].score);
    }

    // 输入要查找的姓名
    char search[11];
    scanf("%s", search);

    // 冒泡排序（按分数降序）
    for (int a = 0; a < n - 1; a++) {
        for (int b = 0; b < n - 1 - a; b++) {
            if (student[b].score < student[b+1].score) {
                report temp;
                strcpy(temp.name, student[b].name);
                temp.score = student[b].score;

                strcpy(student[b].name, student[b+1].name);
                student[b].score = student[b+1].score;

                strcpy(student[b+1].name, temp.name);
                student[b+1].score = temp.score;
            }
        }
    }

    // 二分查找
    int left = 0;
    int right = n - 1;
    int middleIndex;
    int rank;
    while (left <= right ) {
        middleIndex = (int)(left + right) / 2;
        if (strcmp(student[middleIndex].name, search) == 0) {
            rank = middleIndex+1;
            break;
        } else if (strcmp(student[middleIndex].name, search) > 0) {
            left = middleIndex + 1;
        } else if (strcmp(student[middleIndex].name,search) < 0) {
            right = middleIndex - 1;
        }
    }

    // 输出排名
    printf("%d", rank);
    return 0;
}

示例输入 #

Jojo#40
Ray#60
Liz#80
Jojo

排序后结构体数组：[{Liz, 80}, {Ray, 60}, {Jojo,40}]
预期输出：3

错误原因 #

二分查找的核心前提是查找序列必须与比较逻辑的排序规则一致。你现在的数组是按分数降序排序的，但二分查找时却用姓名的字典序来调整左右边界——两者完全不匹配，导致查找逻辑彻底失效。比如示例中排序后的姓名顺序是Liz、Ray、Jojo，而姓名的字典序是Jojo < Liz < Ray，和数组顺序完全相反，二分查找根本无法定位到目标。

修复方案 #

方案1：替换二分查找为遍历查找（推荐） #

由于只有3个学生，遍历查找的效率完全足够，实现简单且不易出错。将原二分查找部分替换为：

int rank = -1; // 初始化标记未找到的情况
for (int i = 0; i < n; i++) {
    if (strcmp(student[i].name, search) == 0) {
        rank = i + 1;
        break;
    }
}

// 处理未找到的情况（可选）
if (rank == -1) {
    printf("未找到该学生");
} else {
    printf("%d", rank);
}

方案2：调整排序规则适配二分查找（若坚持用二分） #

如果一定要使用二分查找，需要将数组按姓名的字典序排序，同时保留分数排名信息。例如，可以在结构体中额外添加rank字段，先按分数排序确定排名，再按姓名排序以支持二分查找：

typedef struct {
    char name[11];
    int score;
    int rank; // 新增排名字段
} report;

// 先按分数降序排序，确定排名
for (int a = 0; a < n - 1; a++) {
    // 原冒泡排序逻辑不变
}
// 给每个学生赋值排名
for (int i = 0; i < n; i++) {
    student[i].rank = i + 1;
}

// 再按姓名字典序排序，适配二分查找
for (int a = 0; a < n - 1; a++) {
    for (int b = 0; b < n - 1 - a; b++) {
        if (strcmp(student[b].name, student[b+1].name) > 0) {
            report temp = student[b];
            student[b] = student[b+1];
            student[b+1] = temp;
        }
    }
}

// 此时二分查找逻辑生效，找到后输出rank字段即可

内容的提问来源于stack exchange，提问作者azio