有效地，使用二进制搜索获得小于给定数字的排序数组中的数字计数

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)方法，而不是尝试编写自己的方法？

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
}

循环¹是必需的，因为javadoc说：

如果数组包含具有指定值的多个元素，则不能保证将找到哪个元素。

^{1）如果例如所有值都相同，例如while}