Как оптимизировать циклы, проходящие через массивы?

Question

Я пошел на www.testdome.com, чтобы проверить свои навыки и открыл список открытых вопросов. Один из вопросов практики был:

Реализация функции CountNumbers, которая принимает отсортированный массив целые и подсчитывает количество элементов массива, которые меньше, чем параметр lessThan.

Например, SortedSearch.CountNumbers (new int [] {1, 3, 5, 7}, 4) должен вернуть 2, потому что есть два элемента массива меньше 4.

И мой ответ был:

using System;

public class SortedSearch
{
    public static int CountNumbers(int[] sortedArray, int lessThan)
    {
        int count = 0;
        int l = sortedArray.Length;

        for (int i = 0; i < l; i++) {
            if (sortedArray [i] < lessThan)
                count++;
        }

        return count;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4));
    }
}

Кажется, я потерпел неудачу по двум причинам:

Performance test when sortedArray contains lessThan: Time limit exceeded
и
Performance test when sortedArray doesn't contain lessThan: Time limit exceeded

Если честно, я не уверен, что там оптимизировать? Может быть, я использую неправильный метод, и есть аналогичный способ ускорить расчет?

Если бы кто-то мог указать на мою ошибку или объяснить, что я делаю не так, я был бы очень признателен!

Answer 1

Должен ли это быть действительно цикл? Вы могли бы сделать лямбда-экспы для этого

public static int CountNumbers(int[] sortedArray, int lessThan)
{
    return sortedArray.ToList().Where(x=>x < lessThan).Count();
}

Answer 2

Ответ и подход Гарольда - точный.

Найдите ниже другой пример кода, если вы готовитесь к техническим собеседованиям. Он обрабатывает случаи, когда массив равен нулю или пуст, когда lessThan представлен в массиве (включая дубликаты) и т. Д.

    private static int CountNumbers(int[] sortedArray, int lessThan)
    {
        if (sortedArray == null)
        {
            throw new ArgumentNullException("Sorted array cannot be null.");
        }

        if (sortedArray.Length == 0)
        {
            throw new ArgumentException("Sorted array cannot be empty.");
        }

        int start = 0;
        int end = sortedArray.Length;
        int middle = int.MinValue;

        while (start < end)
        {
            middle = (start + end) / 2;

            if (sortedArray[middle] == lessThan)
            {
                break; // Found the "lessThan" number in the array, we can stop and move left
            }
            else if (sortedArray[middle] < lessThan)
            {
                start = middle + 1;
            }
            else
            {
                end = middle - 1;
            }
        }

        // Adjust the middle pointer based on the "current" and "lessThan" numbers in the sorted array
        while (middle >= 0 && sortedArray[middle] >= lessThan) 
        {
            middle--;
        }

        // +1 because middle is calculated through 0-based (e.g. start)
        return middle + 1; 
    }

Answer 3

Поскольку массив отсортирован, вы можете прекратить считать, как только достигнете или превысите параметр lessThan.

else break вероятно сделает это.