(C卷,100分)- 小明找位置（Java & JS & Python & C）

题目描述

小朋友出操，按学号从小到大排成一列；

小明来迟了，请你给小明出个主意，让他尽快找到他应该排的位置。

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

输入描述

第一行：输入已排成队列的小朋友的学号（正整数），以","隔开；例如：

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

第二行：小明学号，如：

110

输出描述

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

6

用例

题目解析

本题应该不会存在重复学号问题，因此本题其实就是在一个有序数组中寻找目标值的有序插入位置，可以使用二分法。

关于二分法在有序数组中查找目标值有序插入位置的实现，可以参考：

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const nums = (await readline()).split(",").map(Number);
  const target = parseInt(await readline());

  let idx = binarySearch(nums, target);

  if (idx < 0) {
    idx = -idx - 1;
  }

  // 队列位置（从1开始），因此索引+1
  console.log(idx + 1);
})();

// 参照Java的Arrays.binarySearch实现
function binarySearch(nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    const midVal = nums[mid];

    if (midVal > target) {
      high = mid - 1;
    } else if (midVal < target) {
      low = mid + 1;
    } else {
      return mid; // 如果nums中存在target，则返回target的位置
    }
  }

  return -low - 1; // 如果nums中不存在target，则low就是target在nums中的有序插入位置，为了避免冲突，这里设计为负数返回
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    int target = Integer.parseInt(sc.nextLine());

    // 这里Arrays.binarySearch找不到目标值时，就会返回-low-1，其中low就是目标值的有序插入位置，为什么这么设计返回值，请看解析中外链的博客说明
    int idx = Arrays.binarySearch(nums, target);

    if (idx < 0) {
      idx = -idx - 1;
    }

    // 队列位置（从1开始），因此索引+1
    System.out.println(idx + 1);
  }
}

Python算法源码

# 输入获取
nums = list(map(int, input().split(",")))
target = int(input())


# 算法入口
def binarySearch():
    # 参照Java的Arrays.binarySearch实现
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = (low + high) >> 1
        midVal = nums[mid]

        if midVal > target:
            high = mid - 1
        elif midVal < target:
            low = mid + 1
        else:
            return mid  # 如果nums中存在target，则返回target的位置

    return -low - 1  # 如果nums中不存在target，则low就是target在nums中的有序插入位置，为了避免冲突，这里设计为负数返回


# 算法调用
idx = binarySearch()

if idx < 0:
    idx = -idx - 1

# 队列位置（从1开始），因此索引+1
print(idx + 1)

C算法源码

#include <stdio.h>

#define MAX_SIZE 10000

// 参照Java的Arrays.binarySearch实现
int binarySearch(const int *nums, int nums_size, int target) {
    int low = 0;
    int high = nums_size - 1;

    while (low <= high) {
        int mid = (low + high) >> 1;
        int midVal = nums[mid];

        if (midVal > target) {
            high = mid - 1;
        } else if (midVal < target) {
            low = mid + 1;
        } else {
            return mid; // 如果nums中存在target，则返回target的位置
        }
    }

    return -low - 1; // 如果nums中不存在target，则low就是target在nums中的有序插入位置，为了避免冲突，这里设计为负数返回
}

int main() {
    int nums[MAX_SIZE];
    int nums_size = 0;

    while (scanf("%d", &nums[nums_size++])) {
        if (getchar() != ',') break;
    }

    int target;
    scanf("%d", &target);

    int idx = binarySearch(nums, nums_size, target);

    if (idx < 0) {
        idx = -idx - 1;
    }

    // 队列位置（从1开始），因此索引+1
    printf("%dn", idx + 1);
}