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
#include
#include

template 
void outputVector(std::vector input){
    std::cout  input, double target, int startIndex = 0){
    if(input.size() ::const_iterator begin = input.begin();
        std::vector::const_iterator last = input.begin() + middleIndex;
        std::vector firstHalf(begin, last);
        //std::cout  middle){
        std::vector::const_iterator begin = input.begin() + middleIndex + 1;
        std::vector::const_iterator last = input.begin() + input.size();
        std::vector secondHalf(begin, last);
        //std::cout  doubleVectorInput(){
    std::string inputString;
    getline(std::cin, inputString);
    std::vector array;
    std::istringstream iss(inputString);
    float val;
    while(iss >> val){
        array.push_back(val);
    }
    return array;   
}

int main(){
    double target;
    std::cout  input = doubleVectorInput();
    std::cout > target;
    std::cout << "Target index: " << binarySearch(input, target) << "\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.

StackExchange Code Review Q#154026, answer score: 8