排序搜索可提高性能 [英] sorted search increase performance

问题描述

在testdome上进行练习...目前正在查看 https://www.testdome.com/for-developers/solve-question/9877

Running through exercises on testdome...currently looking at https://www.testdome.com/for-developers/solve-question/9877

实现函数CountNumbers，该函数接受排序的整数数组并计算小于参数lessThan的数组元素的数量.

Implement function CountNumbers that accepts a sorted array of integers and counts the number of array elements that are less than the parameter lessThan.

例如，SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4)应该返回2，因为有两个小于4的数组元素.

For example, SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4) should return 2 because there are two array elements less than 4.

我已经输入:

public class SortedSearch
{
    public static int CountNumbers(int[] sortedArray, int lessThan)
    {
         int returnedValued = 0;

            foreach (int i in sortedArray)
            {
                if(i<lessThan)
                returnedValued += 1;
            }

            return returnedValued;
    }

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

我想知道为什么这会被标记为难易程度，并且预计20分钟才能到达，因为我知道这只需要花费一些时间.无论如何，四分之二的案件通过了.我没有超过时间限制，我想我需要重构以返回更快的搜索.这是正确的吗?如果可以的话，有人可以帮忙吗?

I was wondering why this was marked as difficulty level hard and expected time 20 min when I knew it should only take a few. Anyway, 2 out of 4 cases passed. I'm failing on time limit exceeded and I'm guessing I need to refactor to return a faster search. Is this right? And if so could anyone help with it?

      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

推荐答案

他们希望您使用

They expect you to use the Array.BinarySearch method to get 100%.

using System;

public class SortedSearch
{
    public static int CountNumbers(int[] sortedArray, int lessThan)
    {
        int lengthOfArray = sortedArray.Length;
        if (lengthOfArray == 0) return 0;

        if (sortedArray[0] >= lessThan) return 0;
        if (sortedArray[lengthOfArray - 1] < lessThan) return lengthOfArray;

        int index = Array.BinarySearch(sortedArray, lessThan);
        if (index < 0)
            return ~index;

        return index;
    }

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

这篇关于排序搜索可提高性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！