4
\$\begingroup\$

This is my implementation of a recursive binary search in C++. I'm still a newbie at C++ so:

  • Have I used any bad practices?
  • How could the code be improved upon in terms of efficiency?
  • Could recursion cause a stack overflow error, and if so how can I avoid this?

Criticism is welcome and appreciated!

#include<iostream>
#include<sstream>
#include<vector>

template <typename T>
void outputVector(std::vector<T> input){
    std::cout << "[";
    for(int i = 0; i < input.size(); i++){
        std::cout << input[i];
        if(i != input.size()-1){
            std::cout << ", ";
        }
    }
    std::cout << "]\n";
}

int binarySearch(std::vector<double> input, double target, int startIndex = 0){
    if(input.size() < 2){
        //std::cout << "Closest match found\n";
        return startIndex;
    }

    int middleIndex = int(input.size())/2;
    double middle = input[middleIndex];

    if(target == middle){
        return middleIndex + startIndex; 
    }
    else if(target < middle){
        std::vector<double>::const_iterator begin = input.begin();
        std::vector<double>::const_iterator last = input.begin() + middleIndex;
        std::vector<double> firstHalf(begin, last);
        //std::cout << "First Half: ";
        //outputVector(firstHalf);
        return binarySearch(firstHalf, target, startIndex);
    }
    else if(target > middle){
        std::vector<double>::const_iterator begin = input.begin() + middleIndex + 1;
        std::vector<double>::const_iterator last = input.begin() + input.size();
        std::vector<double> secondHalf(begin, last);
        //std::cout << "Second Half: ";
        //outputVector(secondHalf);
        return binarySearch(secondHalf, target, startIndex+middleIndex+1);
    }
    else{
        return -1;
    }
}


std::vector<double> doubleVectorInput(){
    std::string inputString;
    getline(std::cin, inputString);
    std::vector<double> array;
    std::istringstream iss(inputString);
    float val;
    while(iss >> val){
        array.push_back(val);
    }
    return array;   
}

int main(){
    double target;
    std::cout << "Vector to search: ";
    std::vector<double> input = doubleVectorInput();
    std::cout << "Target: "; std::cin >> target;
    std::cout << "Target index: " << binarySearch(input, target) << "\n";
    return 0;
}

Thank you.

\$\endgroup\$
8
\$\begingroup\$

Space Complexity

This is quite inefficient in terms of the storage space it uses.

Assuming the bisection works as we'd hope, and the vector is cut exactly in half every time, the recursive call copies half the input vector. If, for example, we started with an array of a million items, the first recursive call will copy half a million items. The second recursive call will copy a quarter of a million items.

Since the first call also passed the input array by value, we expect that our search of one million items ends up copying about two million items (in addition to the original vector the user passed).

Time Complexity

Copying those items takes a fair amount of time as well. To be more specific, it takes linear time.

Summary

We normally expect a binary search to have complexity of about \$O(log N)\$, and only descend to \$O(N)\$ in relatively rare worst cases. In this case, we get \$O(N)\$ in about the best case, and \$O(N^2)\$ in the bad cases.

This violates the normal expectations of a binary search badly enough that it effectively only barely qualifies as a binary search at all. In many cases, we can expect its performance to be substantially worse than a simple linear search.

Recommendation

You really don't want to pass the vector by value. Either pass it by reference, along with a pair of indexes into the vector giving the current upper and lower bounds of the part you want to search, or else pass a pair of iterators (there are probably other options as well, but in any case you want to pass an indication of the data to search rather than copying all the data you're going to search).

There are other parts of the code that could use changing as well, but that set of changes is likely to render many (most?) of them obsolete anyway, so I'm not going to get into other areas for now.

\$\endgroup\$
2
\$\begingroup\$

Have I used any bad practices?

Yes. Here are some of them:

  • You have pass vector by value to function when it should be by constant reference (std::vector<T> input).
  • You have not make your algorithm generic enough as it works only for vectors.
  • You declare iterator type explicitly when auto should be used. See previous point.
  • You used int instead of size_t for the size so it might not handle very big vectors.
  • Your limit your binary search to vector of double.
  • You make way too much copy of the data (and thus use a lot of memory).
  • Your binary_search returns an index instead of an iterator.
  • You have made your algorithm recursive when a simple loop would do.
  • You have made easy for your user to call the function specifying an arbitrary index but if a user do so, it will return incorrect result in at least some cases.
  • If the vector is empty, it would return 0 instead of -1.
  • Because of the 2 previous points, the implementation function should be different than the actual function that user should call (usually in a nested namespace) as you use recursivity.
  • In some expression (for example: startIndex+middleIndex+1), you have not using whitespace. Your code should be consistant and readable.
  • last is a poor variable name for end. Usually last mean the position on the last item while endmean the position after the last item. By not conforming to the convention, you make your code harder to understand as one might get mixed up.
  • In a case like that, recursivity can easily be replaced by a loop and might be more efficient (depending on the compiler).
  • Because of some point above, your code is much longer than it need to be.
  • You reinvent the wheel since that algorithm already exist in STL.

How could the code be improved upon in terms of efficiency?

It is not very efficient as already mentioned by others as it copy the data multiple time.

As it is recursive, you will typically copy half the size on first level, one quarter on next level etc... so in the end, you will use almost twice as much memory as you should. And you would more or less have O(n) time complexity instead of O(log n).

At that point, a linear search would be much faster than your code in practice most of the time (because it would be more friendlier which the CPU cache and easier to optimize while having a similar complexity)

Could recursion cause a stack overflow error, and if so how can I avoid this?

It might be a possibility if the compiler decide not the remove recursion. As you copy the vector data, it might make it harder for the compiler to optimize since it is not as easy as to replace the value of a local variable.

In practice, except for large vectors or on embedded device, recursion should not be a problem. Assuming that each recursive call use about 50 bytes and your stack is 1MB, you should be able to handle vector of about 20000 items. This is a rough idea of the magnitude.

Given that you can easily rewrite binary_search without recursivity, the fix is obvious! Use a loop instead and update either begin or last on each iteration.

\$\endgroup\$
-1
\$\begingroup\$

For an algorithm to be classified as a binary search it must have worse-case time complexity of O(log n).

As mentioned by Jerry, here you have a worse case O(N ^2), I suggest you re-think your method.

I'm not sure why you'd perform this operation recursively in C++ (not a great language for such an approach).

\$\endgroup\$
  • \$\begingroup\$ Why would C++ not be great for recursivity? \$\endgroup\$ – Phil1970 Jan 12 at 15:49

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.