java - 使用二分查找高效地获取排序数组中小于给定数字的数字计数

Question

我的问题陈述是这样的 - 查找排序数组中小于给定数字的数字的计数，这应该在时间上有效地完成。我编写了一个使用二分搜索的程序来获取计数，但从时间复杂度角度来看它失败了。需要帮助来实现这一目标。

import java.util.Arrays;

public class SortedSearch {
    public static int countNumbers(int[] sortedArray, int lessThan) {
        if(sortedArray.length ==1 || sortedArray.length == 0) {
            return singleElement(sortedArray, lessThan);
        }
        else {
            return binarySearch(sortedArray, lessThan);
        }
    }

    public static int singleElement(int[] sortedArray, int searchVal) {
        if(sortedArray.length == 0) {
            return 0;
        }
        if(sortedArray[0] < searchVal) {
            return 1;
        }
        return 0;
    }

    private static int binarySearch(int[] sortedArray, int searchVal) {
        int low = 0;
        int high = (sortedArray.length)-1;
        int mid = (low + high)/2;
        if((sortedArray.length == 0) || (sortedArray[0] > searchVal)) {
            return 0;
        }
        if(sortedArray[high] < searchVal) {
            return sortedArray.length;
        }
        if(sortedArray[high] == searchVal) {
            return sortedArray.length-1;
        }
        if(sortedArray[mid] < searchVal) {
            int newLow = low;
            int newHigh = calculateNewHigh(sortedArray, newLow, 0, searchVal);
            int[] newArray = Arrays.copyOfRange(sortedArray, newLow, newHigh+1);
            return newArray.length;
        }
        else {
            int newLow = low;
            int newHigh = mid;
            int[] newArray = Arrays.copyOfRange(sortedArray, newLow, newHigh+1);
            return binarySearch(newArray, searchVal);
        }
    }

    private static int calculateNewHigh(int[] sortedArray, int low, int previousHigh, int searchVal) {
        int newHigh =  previousHigh + (sortedArray.length-low)/2;
        if(sortedArray[newHigh] < searchVal) {
            newHigh = calculateNewHigh(sortedArray, newHigh, newHigh, searchVal);
        }
        if(sortedArray[newHigh] == searchVal) {
            newHigh--;
        }
        if(sortedArray[newHigh] > searchVal) {
            newHigh--;
        }
        return newHigh;
    }

    public static void main(String[] args) {
        System.out.println(SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4));
    }
}

Answer 1

既然你无论如何都在使用Arrays，那就不要使用Arrays.binarySearch(int[] a, int key)方法，而不是尝试编写自己的方法？

public static int countNumbers(int[] sortedArray, int lessThan) {
    int idx = Arrays.binarySearch(sortedArray, lessThan);
    if (idx < 0)
        return -idx - 1; // insertion point
    while (idx > 0 && sortedArray[idx - 1] == lessThan)
        idx--;
    return idx; // index of first element with given value
}

while循环¹是必要的，因为javadoc说:

If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

^{1) 如果例如，此循环不是最佳循环所有值都相同，请参见例如Finding multiple entries with binary search}