Сортировка поиска, количество номеров меньше целевого значения

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;
    }

И результат, который я получаю, когда тестирую его в своей среде, выглядит следующим образом

Пример: правильный ответ
Различные маленькие массивы: правильные ответ
Тест производительности, когда sortedArray содержит lessThan: Превышен лимит времени
Тест производительности, когда sortedArray не содержит lessThan: Превышен лимит времени

, поэтому два теста производительности не пройдены, хотя я этого не вижу тесты могут быть, я мог бы получить предложение здесь

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;

Если ключ не найден, он возвращает отрицательную позицию вставки. Чтобы преобразовать его в индекс, я сделал + 1 и умножил на - 1, чтобы сделать его положительным.