提高二进制搜索的复杂度，计算更高和更低元素的数量？

Question

Java Array有一个binarySearch方法，它返回数组中给定键的索引。但是，如果存在重复项，则此binarySearch不保证将找到哪个元素

例：

• 数字数组给出[5 8 7 2 4 3 7 9 1 9]。
• 对此数组排序[1 2 3 4 5 7 7 8 9 9]。
• 使用给定密钥对其执行二进制搜索。
• 对于返回的每个索引，打印低于和高于它的元素数。

对于关键的7，给出了索引5 - 较小元素的数量将是“5”并且更大将是“3”，因为有2个7。

对于键'0'，将给出索引'-1'，因为没有小于它的元素。 Smaller: 0, Greater: 10.

对于键'100'，将给出索引'-11'，因为没有大于它的元素。 Smaller: 10, Greater: 0.

对于键'6'，将给出索引'-6'。数组中不存在元素。 Smaller: 5, Greater: 5.

算法：

public class Counting {
    private void run() {
        Scanner sc = new Scanner(System.in);
        int no_digits = Integer.parseInt(sc.nextLine());
        int[] digits = new int[no_digits];
        for (int i = 0; i < no_digits; i++) {
            digits[i] = sc.nextInt();
        }
        sc.nextLine();
        Arrays.sort(digits);

        int no_queries = Integer.parseInt(sc.nextLine());

        for (int i = 0; i < no_queries; i++) {
            int key = sc.nextInt();
            int upper = 0;
            int lower = Arrays.binarySearch(digits, key);

            if(lower == -1){
                lower = 0;
                upper = no_digits;
            }else if(Math.abs(lower) > no_digits){
                lower = no_digits;
                upper = 0;
            }else if(lower <= 0){
                lower = Math.abs(lower) - 1;
                upper = no_digits - lower;
            } else {
                int value = digits[lower];
                int j = 0;
                int k = 0;

               high: while(digits[lower + j] == value){
                    j++;
                    if((lower + j) > no_digits - 1){
                        break high;
                    }
                }

                upper = no_digits - lower - j;

                low: while(digits[lower - k] == value){
                    k++;
                    if((lower - k) < 0){
                        break low;
                    }
                }

                lower = lower - k + 1;

            }
            System.out.println("Smaller: " + lower + ", Greater: " + upper);
        }
        sc.close();      
    }

    public static void main(String[] args) {
        Counting newCounting = new Counting();
        newCounting.run();
    }
}

这是有效的，但是其中一个测试用例具有算法从头到尾多次遍历数组，这导致算法花费相当多的时间来完成。

示例：一个100位数字的数组，其中前半部分的数字是1，后半部分是100。

如果我搜索1，索引可能会返回34，因为无法保证找到哪个索引。然后我的算法将从索引34两个方向遍历数组，以获得Smaller: 0, Greater: 50，因为数组的上半部分都是数字100。

有没有办法让这个更有效率？我的目标是O((N+Q) log N)复杂性，其中Q是查询数，K是数组中的整数数。

Answer 1

看来你可以使用Map作为coutning元素，使用TreeMap进行排序。 Bor大数据，最好预先计算一些数据，然后将其用于您的目标。这是这个想法的近似例子：

public class Counting {
    private static NavigableMap<Integer, Integer> read(Scanner scan, int no_digits) {
        // put keys in the reverce order; key - digit, value - times in input
        TreeMap<Integer, Integer> map = new TreeMap<>((key1, key2) -> Integer.compare(key2, key1));

        for (int i = 0; i < no_digits; i++) {
            int digit = scan.nextInt();
            map.put(digit, map.getOrDefault(digit, 0) + 1);
        }

        return map;
    }

    private static int[] calculate(int key, NavigableMap<Integer, Integer> map, int no_digits) {
        int lower = 0;
        int upper = no_digits;

        if (map.containsKey(key)) {
            // for existed keys, get tail of reverce and get first element
            lower = map.tailMap(key, false).firstEntry().getKey();
            // for existed keys, get actual count and increment it
            upper = map.getOrDefault(key, -1) + 1;
        }

        return new int[] { lower, upper };
    }

    public static void main(String[] args) {
        try (Scanner scan = new Scanner(System.in)) {
            int no_digits = scan.nextInt();
            NavigableMap<Integer, Integer> map = read(scan, no_digits);
            int no_queries = scan.nextInt();

            for (int i = 0; i < no_queries; i++) {
                int[] res = calculate(scan.nextInt(), map, no_digits);
                System.out.println("Smaller: " + res[0] + ", Greater: " + res[1]);
            }
        }
    }
}