java - 使用二进制搜索来计算小于/大于给定数字的元素数

Question

给定一个数字current，找出数组中大于和小于该值的值的数量。

//sort array for binary search
 int[] digits = Arrays.stream(sc.nextLine()
            .split(" "))
            .mapToInt(Integer::parseInt)
            .sorted()
            .toArray();

//for duplicate values, find higher index of current.

   while(low <= high){
        int mid = low + (high - low)/2;
        if(digits[mid] > current){
            high = mid - 1;
        }else if (digits[mid] == current){
            startindex = mid;
            high = mid - 1;   
        }else{
            startindex = mid;
            low = mid +1;
        }
    }

//for duplicate values, find lower index of current.
    int endindex = -1;
    low = 0;
    high = no_digits - 1;

    while(low <= high){
        int mid = low + (high - low)/2;
        if(digits[mid] > current){
            high = mid - 1;
        }else if (digits[mid] == current){
            endindex = mid;
            low = mid + 1;   
        }else{
            endindex = mid;
            low = mid + 1;
        }
    }

    System.out.println(endindex + "-" + startindex);

    if(digits[0] > current){
        smallest = 0;
        largest = no_digits;
        System.out.println(String.format("Smaller: %d, Greater: %d", smallest, largest));
    } else if (digits[no_digits - 1] < current){
        smallest = no_digits;
        largest = 0;
        System.out.println(String.format("Smaller: %d, Greater: %d", smallest, largest));
    }else {
        smallest = startindex;
        largest = no_digits - endindex - 1;                
        System.out.println(String.format("Smaller: %d, Greater: %d", smallest, largest));
    }
}

示例输入:

5 8 7 2 4 3 7 9 1 9 - Array of ints.

7
0
100
3
6

输出:

Smaller: 5, Greater: 3
Smaller: 0, Greater: 10
Smaller: 10, Greater: 0
Smaller: 2, Greater: 7
Smaller: 5, Greater: 5

我的结果:

6-5 //start and end index.
Smaller: 5, Greater: 3
-1--1 
Smaller: 0, Greater: 10
9-9
Smaller: 10, Greater: 0
2-2
Smaller: 2, Greater: 7
4-4
Smaller: 5, Greater: 4

我设法提出了上述算法，该算法考虑了大于或小于数组中任何值的值。

但是，由于我需要在 O((N+Q) log N) 时间内完成上述操作，因此我无法在不遍历数组的情况下找到解决数组中不存在的值的解决方案。

在这种情况下，这将是值为 6 的最后一个测试用例。数组中不存在 6，但我仍需要计算所有高于/低于 6 的值。

Answer 1

二进制搜索算法为数组中不存在的值生成“插入点”。您的 startIndex 和 endIndex 将为您提供第一个“符合条件”的项目，或者紧挨着它的项目。换句话说，如果您要查找小于 6 的所有值，则搜索端点将产生 5 的索引。

请注意，您不需要推出自己的二进制搜索算法:Java 为您提供了一个实现。

引用:Arrays.binarySearch