小明找位置（C语言）【二分查找】_python 小朋友出操,按学号从小到大排成一列; 小明来迟了,请你给小明出个主意,让他

题目来自于博主算法大师的专栏：最新华为OD机试C卷+AB卷+OJ（C++JavaJSPy） https://blog.csdn.net/banxia_frontend/category_12225173.html

题目描述

小朋友出操，按学号从小到大排成一列；小明来迟了，请你给小明出个主意，让他尽快找到他应该排的位置。

算法复杂度要求不高于 nLog(n)；学号为整数类型，队列规模<=10000；

输入描述

1、第一行：输入已排成队列的小朋友的学号（正整数），以”,”隔开；
例如：93,95,97,100,102,123,155
2、第二行：小明学号，如 110；

输出描述

输出一个数字，代表队列位置（从 1 开始）。

例如：

6
1

示例一

输入

93,95,97,100,102,123,155
110
1
2

输出

6
1

OD 统一题解

将已排好序的学号列表转换成整数列表，然后使用二分查找找到小明应该插入的位置

代码

// 小明找位置问题的解决方案，通过二分查找算法实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 10001

// 定义二分查找函数，输入参数：整数数组id、数组长度count以及需要查找的学号num
int find(int id[], int count, int num) {
    // 初始化二分查找的左右边界
    int left = 0, right = count - 1;

    // 当左边界小于等于右边界时继续循环
    while (left <= right) {
        // 计算中间位置的索引
        int mid = (left + right) / 2;
        
        // 检查中间位置的学号与目标学号的关系
        if (id[mid] < num) { // 如果中间位置的学号小于目标学号
            left = mid + 1; // 移动左边界到中间位置右侧
        } else if (id[mid] > num) { // 如果中间位置的学号大于目标学号
            right = mid - 1; // 移动右边界到中间位置左侧
        } else { // 如果找到目标学号，则返回该位置的索引
            return mid;
        }
    }

    // 若未找到目标学号，返回小明应插入的位置（即左边界+1）
    return left;
}

int main() {
    // 读取已排序学号字符串
    char input[MAX_LEN];
    fgets(input, MAX_LEN, stdin);
    input[strcspn(input, "\n")] = '\0'; // 去掉末尾换行符

    // 存储转换为整数的学号数组
    int id[MAX_LEN];
    int count = 0;

    // 使用strtok函数按逗号分割输入字符串，并将每个学号转换为整数存入数组
    char *token = strtok(input, ",");
    while (token != NULL) {
        id[count++] = atoi(token); // 将字符串学号转换为整数并存储
        token = strtok(NULL, ","); // 继续处理下一个学号
    }

    // 读取小明的学号
    int num;
    scanf("%d", &num);

    // 调用二分查找函数找出小明应在队列中的位置
    int res = find(id, count, num);

    // 输出结果，由于队列位置从1开始计数，所以输出时+1
    printf("%d\n", res + 1);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

注意：while (left <= right) 有等号