Binary search feedback and improvements

You don't need to floor the result of an integer division: the result is exactly the same without it.

When getting the mid value, this is safer:

mid = lo + (hi - lo) / 2;

This way you'll be safe from integer overflows, which can happen when adding two very large integers. (Or long, you get the point)

As you notice, there is some redundancy in the logic of seeing the mid before the main while loop and then again inside the loop, and also in the conditions within the loop and after it. Probably you can refactor this without redundancies, with most logic inside the loop, and almost nothing outside. There should be a return statement inside the loop when the element is found. The empty check will become unnecessary, as the loop condition will never be true for empty input.

template<class T>
long binary_search(const std::vector<T>& v, const T& key){
    long lo = 0;
    long hi = v.size();

    while (lo < hi) {
        long mid = lo + (hi - lo ) / 2; 

        if (v[mid] == key) {
            return mid;
        }
        if (v[mid] < key) {
            lo = mid + 1; 
        } else {
            hi = mid - 1; 
        }
    }

    return -1; 
}

• The typical problem with bsearch-like functions is their interface:

  • If the array has more than one matching element, the returned one is pretty much random.
  • Returning -1 when there key doesn't match anything throws away valuable information.

  A solution offered by STL is lower_bound, and I highly recommend to follow its specification.

• It is much simpler to work on semi-open ranges. Your code doesn't depend on v[hi], so hi = v.size() - 1 only complicates the matters. In particular pmid and related comparisons would simply vanish.

• Consider passing a comparison function (defaulted to std::less) as an argument.

• mid > 0 is much more idiomatic than m - 1 >= 0.