Binary Search implemented in C++ 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&lt;iostream&gt;
#include&lt;sstream&gt;
#include&lt;vector&gt;

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

int binarySearch(std::vector&lt;double&gt; input, double target, int startIndex = 0){
    if(input.size() &lt; 2){
        //std::cout &lt;&lt; "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 &lt; middle){
        std::vector&lt;double&gt;::const_iterator begin = input.begin();
        std::vector&lt;double&gt;::const_iterator last = input.begin() + middleIndex;
        std::vector&lt;double&gt; firstHalf(begin, last);
        //std::cout &lt;&lt; "First Half: ";
        //outputVector(firstHalf);
        return binarySearch(firstHalf, target, startIndex);
    }
    else if(target &gt; middle){
        std::vector&lt;double&gt;::const_iterator begin = input.begin() + middleIndex + 1;
        std::vector&lt;double&gt;::const_iterator last = input.begin() + input.size();
        std::vector&lt;double&gt; secondHalf(begin, last);
        //std::cout &lt;&lt; "Second Half: ";
        //outputVector(secondHalf);
        return binarySearch(secondHalf, target, startIndex+middleIndex+1);
    }
    else{
        return -1;
    }
}


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

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


Thank you.
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.