• Post Reply Bookmark Topic Watch Topic
  • New Topic

Solving SortedSearch test  RSS feed

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi! I'm trying to solve this test:
https://www.testdome.com/questions/java/sorted-search/11890?questionIds=11890,11909&generatorId=27&type=fromtest&testDifficulty=Hard
Implement function countNumbers that accepts a sorted array of integers and counts the number of array elements that are less than the parameter lessThan.

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


I can get the basic tests to pass but I fail both performance tests. How can I speed this up?

This is what I have tried:


and

 
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seems like you could do something along the lines of a binary search. Undoubtedly they are throwing a huge list at your code causing the timing issue.
 
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As it is an array that is already ordered, a sequential search can be very slow. Try a binary search.
 
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A straight binary search may give you the wrong answer. What happens if you have a large array containing multiple 4s? Binary search will find a 4's index, but it will find any 4, not necessarily find the first, so you don't know the index of the first 4, which is one more than the index of the last 3. Once you have the index of the first 4, the count is very simple to calculate.
 
Carl Anton
Greenhorn
Posts: 8
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the tips.
Binarysearch put me on the right path.
This code did the trick, I don't know, it feels a bit convoluted, but the tests pass!

 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It isn't that convoluted, but you might do well to repeat the code, and annotate it with an explanation of what each part does.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!