华为od算法题-小明找位置-Java解法

华为od算法题-小明找位置-Java解法

题目

小明友出操，按学号从小到大排成一列；小明来迟了，请你给小明出个主意，让他尽快找到他应该排的位置。 算法复杂度要求不高于nLog（n）；学号为堅数类型，队列规模<=10000； 输入描述： 1、第一行：输入已排成队列的小朋友的学号（正整数），以”,”1隔开； 例如：93 95 97 100 102 123 155 2、第二行：小明学号，如110； 输出描述： 输出一个数字，代表队列位置（从1开始）。 例如： 6 示例1 输入 93 95 97 100 102 123 155 110 输出 6

思路

遍历数组，用二分查找得到小明应该插入的下标

解题方法

二分查找

复杂度

时间复杂度 O(log(n))

空间复杂度 O(1)

代码

public static int getLocation(String[] nums, int id){
        int loc = 0;
        int left = 0, right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(Integer.valueOf(nums[mid])> id){
                right = mid -1;
            } else if(Integer.valueOf(nums[mid]) < id){
                left = mid + 1;
            } else {
                return mid+1;
            }
        }
        return left+1;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] nums = s.split(" ");
        int id = sc.nextInt();
        sc.close();
        System.out.println(getLocation(nums, id));
    }