时间戳

首页 > 解决方案 > 如何有效地计算排序数组中小于某个值的元素？

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

问题描述

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

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

和一个关键值80

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

标签： javaarrayssorting

解决方案

您可以使用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)-1or -(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).

推荐阅读