华为OD机试 - 小明找位置 - 二分查找（Python/JS/C/C++ 2024 E卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

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

二、输入描述

第一行: 输入已排成队列的小朋友的学号 (整数数)，以","隔开

例如: 93,95,97,100,102,123,155

第二行: 小明学号，例如 110；

三、输出描述

输出一个数字，代表队列位置(从 1 开始)

例如: 6

四、测试用例

测试用例1：

1、输入

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

2、输出

3、说明

小明的学号是110，队列按升序排列：

93, 95, 97, 100, 102, 123, 155

根据二分查找，110应该插入的位置是102之后、123之前，因此返回的排队位置是6（从1开始计数）。

测试用例2：

1、输入

1,5,10,15,20,25,30
18

2、输出

3、说明

小明的学号是18，队列按升序排列：

1, 5, 10, 15, 20, 25, 30

根据二分查找，18应该插入在15之后、20之前，因此返回的排队位置是5。

五、解题思路

我们可以利用Java的Arrays.binarySearch方法来实现二分查找，如果没有找到精确匹配的位置，binarySearch会返回负数，我们可以根据这个负数值推断出插入点。

首先，将输入的队列学号进行处理，将字符串转换为整型数组。
采用二分查找（Binary Search）的方式，找到小明应该插入的位置。
根据找到的位置输出正确的排队位置（从1开始计数）。

六、Python算法源码

import bisectdef find_position(queue, xiaoMingID):# 使用bisect库进行二分查找index = bisect.bisect_left(queue, xiaoMingID)# 如果找到了小明的学号，返回实际位置 + 1（从1开始的索引）if index < len(queue) and queue[index] == xiaoMingID:return index + 1# 如果没找到，返回应该插入的位置（也是从1开始的索引）return index + 1def main():# 读取输入的学号队列input_queue = input().strip()queue_array = input_queue.split(",")# 转换成整数列表queue = [int(num.strip()) for num in queue_array]# 读取小明的学号xiaoMingID = int(input().strip())# 使用二分查找来找到小明应该插入的位置position = find_position(queue, xiaoMingID)# 输出结果，position已经是从1开始的索引print(position)# 测试程序
if __name__ == "__main__":main()

七、JavaScript算法源码

function findPosition(queue, xiaoMingID) {// 使用二分查找查找小明的插入位置let left = 0;let right = queue.length - 1;// 二分查找算法while (left <= right) {let mid = Math.floor((left + right) / 2);if (queue[mid] === xiaoMingID) {return mid + 1; // 找到了小明的学号，返回从1开始的位置} else if (queue[mid] < xiaoMingID) {left = mid + 1;} else {right = mid - 1;}}// 如果没有找到，left即为小明应插入的位置，返回从1开始的索引return left + 1;
}function main() {// 读取输入的学号队列let inputQueue = prompt("请输入学号队列 (以逗号分隔):");let queueArray = inputQueue.split(",");// 转换成整数数组let queue = queueArray.map(num => parseInt(num.trim()));// 读取小明的学号let xiaoMingID = parseInt(prompt("请输入小明的学号:"));// 使用二分查找查找小明应该插入的位置let position = findPosition(queue, xiaoMingID);// 输出结果，position已经是从1开始的索引console.log(position);
}// 调用主函数
main();

八、C算法源码

#include <stdio.h>int findPosition(int queue[], int size, int xiaoMingID) {int left = 0;int right = size - 1;// 二分查找算法while (left <= right) {int mid = (left + right) / 2;if (queue[mid] == xiaoMingID) {return mid + 1; // 找到了小明的学号，返回从1开始的位置} else if (queue[mid] < xiaoMingID) {left = mid + 1;} else {right = mid - 1;}}// 如果没找到，返回插入位置（从1开始的索引）return left + 1;
}int main() {char inputQueue[100];int queue[100], size = 0, xiaoMingID;// 读取输入的学号队列printf("请输入学号队列 (以逗号分隔): ");fgets(inputQueue, sizeof(inputQueue), stdin);// 将输入的字符串转换成整数数组char *token = strtok(inputQueue, ",");while (token != NULL) {queue[size++] = atoi(token);token = strtok(NULL, ",");}// 读取小明的学号printf("请输入小明的学号: ");scanf("%d", &xiaoMingID);// 使用二分查找来找到小明应该插入的位置int position = findPosition(queue, size, xiaoMingID);// 输出结果，position已经是从1开始的索引printf("%d\n", position);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>using namespace std;// 使用二分查找来找到小明的插入位置
int findPosition(const vector<int>& queue, int xiaoMingID) {int left = 0;int right = queue.size() - 1;// 二分查找算法while (left <= right) {int mid = left + (right - left) / 2;if (queue[mid] == xiaoMingID) {return mid + 1; // 找到了小明的学号，返回从1开始的位置} else if (queue[mid] < xiaoMingID) {left = mid + 1;} else {right = mid - 1;}}// 如果没有找到，left 即为小明应插入的位置，返回从1开始的索引return left + 1;
}int main() {string inputQueue;vector<int> queue;int xiaoMingID;// 读取输入的学号队列cout << "请输入学号队列 (以逗号分隔): ";getline(cin, inputQueue);stringstream ss(inputQueue);string token;// 将输入的字符串转换成整数数组while (getline(ss, token, ',')) {queue.push_back(stoi(token));}// 读取小明的学号cout << "请输入小明的学号: ";cin >> xiaoMingID;// 使用二分查找查找小明应该插入的位置int position = findPosition(queue, xiaoMingID);// 输出结果，position已经是从1开始的索引cout << position << endl;return 0;
}