java - 排序搜索，计数小于目标值的数字

Question

我正在练习排序搜索任务，来自 testdome.com

/**
 * Implement function countNumbers that accepts a sorted array of unique integers and,
 * efficiently with respect to time used, counts the number of array elements that are less than the parameter lessThan.
 * <p>
 * For example, SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4)
 * should return 2 because there are two array elements less than 4.
 */

目前，根据该网站，由于边缘情况和性能，我的答案得分为 50%，我试图就我可能需要添加的内容或不同的方法发表意见。
这是我的代码

 public static int countNumbers(int[] sortedArray, int lessThan) {
        int count = 0;
        if(sortedArray == null) {
            return 0;
        }
        List<Integer> numbers  = new ArrayList<>();
        for (int i = 0; i < sortedArray.length; i++) {
            if (sortedArray[i] < lessThan) {
                count++;
            } else  {
                break;
            }
        }
        return count;
    }

我在他们的环境中测试时得到的结果如下

Example case: Correct answer
Various small arrays: Correct answer
Performance test when sortedArray contains lessThan: Time limit exceeded
Performance test when sortedArray doesn't contain lessThan: Time limit exceeded

所以两个性能测试失败了，即使我看不到这个测试可能是我可以在这里得到建议

Answer 1

如 O(n)正在给 TLE。您需要比 O(n) 更快的东西.二分查找是 O(logN) .

public static int countNumbers(int[] sortedArray, int lessThan) {
    int start = 0;
    int end = sortedArray.length - 1;
    int mid = 0;
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (sortedArray[mid] < lessThan) {
            if (mid < sortedArray.length - 1 && sortedArray[mid + 1] < lessThan) {
                start = mid + 1;
                continue;
            } else {
                return mid + 1;
            }
        }

        if (sortedArray[mid] >= lessThan) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return 0;
}

或者使用内置的二分搜索:

Arrays.binarySearch(new int[]{1, 2, 4}, 3) + 1) * -1;

当未找到 key 时，它返回负插入位置。要将其转换为索引，我做了 + 1并乘以 - 1使其积极。