Performance in vector search

[Amaris]

How can I enhance performance here?

Assignment:

Implement function countNumbers that accepts a sorted vector of unique integers and counts the number of vector elements that are less than the parameter lessThan.

For example, for vector v containing { 1, 3, 5, 7 }, SortedSearch::countNumbers(v, 4) should return 2 because there are two vector elements less than 4.

My code:

#include <vector>
#include <stdexcept>
#include <iostream>
#include <algorithm>

class SortedSearch
{
public:
    static int countNumbers(const std::vector<int>& sortedVector, 
        int lessThan)
    {   
        int count = 0;
        
        if (sortedVector.size() == 1)
        {
            if (sortedVector[0] < lessThan)
            {
                count++;
            }                
            return count;
        }
        
        
        int halfSize = sortedVector.size()/2;          
        std::vector<int> halfVector;
        
        if (sortedVector[halfSize - 1] < lessThan)
        {
            count = halfSize;
            halfVector.assign(sortedVector.begin()+halfSize,
                              sortedVector.end());
        }
        else
        {
            halfVector.assign(sortedVector.begin(),
                              sortedVector.begin()+halfSize);
        }
        
        count += countNumbers(halfVector, lessThan);
        return count;
    }
    
};

#ifndef RunTests
int main()
{
    std::vector<int> v { 1, 2, 3, 5, 7 };
    std::cout << SortedSearch::countNumbers(v, 4);
}
#endif

[Repeater]

You are rebuilding the vector object every time you reduce the search space. That's expensive. Don't do that.

[keskiverto]

Code tags on post would help reading.

You do use recursion and do copy vectors, don't you?
Copies need time and memory.

The std has upper_bound, lower_bound, and equal_range.
They don't recurse or copy.

With vector's iterator's you can compute distance O(1).

#include <algorithm>    // std::upper_bound
#include <vector>       // std::vector

int main () {
  std::vector<int> v { 1, 2, 3, 5, 7 };
  auto foo = std::upper_bound( v.begin(), v.end(), 4 );
  // foo points to the 5, to the foo[3]
  auto distance = foo - v.begin();
  // distance == 3 and there are 3 elements before foo[3]
  return 0;
}

Do note that 5 is not less than 5. Therefore,
std::upper_bound( v.begin(), v.end(), 5 ) - v.begin()
returns 4, not 3.

Some adjustments to logic?

[jonnin]

its sorted already. you can do a modified binary search to find the location in the array where the value to the left is < lessthan and the right is > lessthan. Take the right value's index. You have that many values less than it. I think this is the fastest way to get the answer. Of course you need to watch for edge cases etc. Which is pretty much what the above does, in English.

[Amaris]

@keskiverto

auto foo = std::upper_bound( v.begin(), v.end(), 4 );

does the trick although its

auto foo = std::upper_bound( v.begin(), v.end(), 3 );

since I want the amount of all elements < 4 and upper_bound points to the first element > 4

[helios]

Then you should use std::lower_bound(), which will return an iterator to the first element that is >= the search term.

[Amaris]

Without coping the vector and using only iterators
(could have also been indexes)

The more efficient code results to

class SortedSearch
{
public:
    static int countNumbers(const std::vector<int>& sortedVector, int lessThan)
    {           
        return countNum(sortedVector.begin(), sortedVector.end(), lessThan);
    }
    
    static int countNum( std::vector<int>::const_iterator begin, std::vector<int>::const_iterator end, 
int lessThan)
    {
        int count = 0;
        int size = std::distance(begin, end);
        
        if (size == 1)
        {
            if (*begin < lessThan)
            {
                count++;
            }                
            return count;
        }
                
        int halfSize = size/2;
        
        if (*(begin + halfSize - 1) < lessThan)
        {
            count = halfSize;
            count += countNum( begin+halfSize, end, lessThan );
        }
        else
        {
            count += countNum(begin, end-halfSize, lessThan);
        }
        return count;
    }
    
};

which is quite similar to what std::upper_bound does internally however without recursion

[keskiverto]

Never said that upper_bound is the correct solution. Lower ...

#include <algorithm>    // std::lower_bound
#include <vector>       // std::vector
#include <iostream>

int main () {
  std::vector<int> v { 1, 2, 2, 2, 3, 5, 7 };
  for ( int x=0; x < 10; ++x ) {
    auto foo = std::lower_bound( v.begin(), v.end(), x );
    std::cout << x << ": " << foo - v.begin() << " {";
    for ( auto it = v.begin(); it != foo; ++it ) std::cout << ' ' << *it;
    std::cout << " }\n";
  }
  return 0;
}

0: 0 { }
1: 0 { }
2: 1 { 1 }
3: 4 { 1 2 2 2 }
4: 5 { 1 2 2 2 3 }
5: 5 { 1 2 2 2 3 }
6: 6 { 1 2 2 2 3 5 }
7: 6 { 1 2 2 2 3 5 }
8: 7 { 1 2 2 2 3 5 7 }
9: 7 { 1 2 2 2 3 5 7 }

Edit:

#include <algorithm>
#include <vector>
#include <iostream>
#include <functional>

int main () {
  std::vector<int> v { 1, 2, 2, 2, 3, 5, 7 };
  for ( int x=0; x < 10; ++x ) {
    auto foo = std::upper_bound( v.begin(), v.end(), x, std::less_equal<int>() );
    std::cout << x << ": " << foo - v.begin() << " {";
    for ( auto it = v.begin(); it != foo; ++it ) std::cout << ' ' << *it;
    std::cout << " }\n";
  }
  return 0;
}

0: 0 { }
1: 0 { }
2: 1 { 1 }
3: 4 { 1 2 2 2 }
4: 5 { 1 2 2 2 3 }
5: 5 { 1 2 2 2 3 }
6: 6 { 1 2 2 2 3 5 }
7: 6 { 1 2 2 2 3 5 }
8: 7 { 1 2 2 2 3 5 7 }
9: 7 { 1 2 2 2 3 5 7 }