triés d'augmenter les performances de recherche

Question

en cours grâce à des exercices sur testdome ... actuellement à la recherche à https://www.testdome.com/for-developers/solve-question/9877

Mettre en œuvre la fonction CountNumbers qui accepte un tableau trié d'entiers et compte le nombre d'éléments du tableau qui sont inférieur au paramètre lessThan.

Par exemple, SortedSearch.CountNumbers(new int[] { 1, 3, 5, 7 }, 4) devrait revenir 2 parce qu'il ya deux éléments du tableau moins 4.

Je suis entré:

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

Je me demandais pourquoi cela a été marqué comme niveau de difficulté difficile et temps prévu 20 min quand je savais que cela ne devrait prendre que quelques-uns. Quoi qu'il en soit, 2 cas sur 4 sont passés. J'échoue sur la limite de temps dépassée et je devine que j'ai besoin de refactoriser pour retourner une recherche plus rapide. Est-ce correct? Et si oui, est-ce que quelqu'un pourrait l'aider?

  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

Vous devriez avoir à briser la boucle foreach, une fois si état obtenir de faux parce que nous savons déjà tableau donné est triée donc il n'y a pas de point de continuer à évaluer d'autres éléments. Veuillez voir ci-dessous l'extrait de code pour référence.

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

Veuillez voir ci-dessous la solution qui a passé tous les 4 tests. J'ai utilisé la technique de recherche binaire pour trouver l'élément qui est plus grand que lessThan variable.

public static int CountNumbers(int[] sortedArray, int lessThan) 
{ 
    //Handle all the corner cases 
    int legthOfArray = sortedArray.Length; 
    if (legthOfArray == 0) return 0; 
    if (sortedArray[0] >= lessThan) return 0; 
    if (sortedArray[legthOfArray - 1] < lessThan) return legthOfArray; 
    return FindIndexGreaterOrEqualIndex(sortedArray, legthOfArray, lessThan, legthOfArray/2); 
} 

public static int FindIndexGreaterOrEqualIndex(int[] sortedArray, int lengthOfArray, int lessThan, int currentIndex) 
{ 
    while (true) 
    { 
     bool isCurrentElementLessThan = sortedArray[currentIndex] < lessThan; 
     if (isCurrentElementLessThan) // Traverse Right hand side of binary tree. 
      currentIndex = (int)Math.Ceiling((decimal)(currentIndex + lengthOfArray - 1)/2); 
     else if (sortedArray[currentIndex - 1] < lessThan && !isCurrentElementLessThan) //If array element is not less than and previous element is less than the given element. i.e. our answer so break the loop. 
      break; 
     else // Traverse Left hand side of binary tree. 
      currentIndex = (int)Math.Ceiling((decimal)currentIndex/2); 
    } 
    return currentIndex; 
} 

Jetez un oeil :)

Answer 2

Ils vous attendent à utiliser la méthode Array.BinarySearch pour obtenir 100%.

using System; 

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

     int lengthOfArray = sortedArray.Length; 
     if (lengthOfArray == 0) 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)); 
    } 
}