如何有效地计算排序数组中小于某个值的元素？

html5 • • 问答

比如说我有一个排序数组：

[21, 32, 58, 70, 100, 4342]

和一个关键值 80

如何在不使用 if 条件遍历整个数组的情况下有效地计算 80 以下的所有值？我在想二进制搜索，但又一次我没有搜索任何键，我只需要最快的方法返回小于或等于键值的值的计数。

回答

您可以使用Arrays.binarySearch. 根据文档，它返回搜索键(-(insertion point) - 1)的索引，如果它包含在数组中；否则，。使用您的示例：

import java.util.Arrays;

class Main {
    public static void main(String args[]) {
        int[] arr = {21, 32, 58, 70, 100, 4342};

        int res70 = Arrays.binarySearch(arr, 70);// returns 3
        int res80 = Arrays.binarySearch(arr, 80);// returns -5
    }
}

考虑到这一点，您可以使用该信息来获得有效计数：如果结果为正，则计数为result + 1，如果结果为负，则计数为(-result)-1或-(result+1)（取决于您的偏好）：

import java.util.Arrays;

class Main {
    public static void main(String args[]) {
        int[] arr = {21, 32, 58, 70, 100, 4342};

        System.out.println("Count is:" + count(arr, 70));// returns 4
        System.out.println("Count is:" + count(arr, 80));// returns 4
    }

    private static int count(int[] sortedArray, int n) {
        int result = Arrays.binarySearch(sortedArray, n);
        if (result > -1) {
            return (result + 1);
        }
        return (-result) - 1;
    }
}

对于可能出现重复，且数组中存在多个80的情况，有两种可能的解决方案：

  1. 从二分搜索的结果中进行线性搜索。O(n)虽然这将是最坏的情况，但仍然是O(lg n)平均水平。

  2. 手动实现（或查找具有）二分查找的库以查找与某个值相等的最后一个元素（同时保留对未找到的元素的考虑，就像 Java 库所做的那样）。此答案中存在查找最后一个元素的示例：Last index of multiple keys using binary-search? 这将使最坏的情况保持在O(lg n).

  • No problem. Also, welcome to SO. To be honest, I couldn't think of the solution you provided in the edit. Nice job done. This should be the answer now (because it is more complete).
  • I know that we were probably writing the answer at the same time, but please make sure all special cases are handled properly. 1+ for giving example code.
以上是如何有效地计算排序数组中小于某个值的元素？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>