3
\$\begingroup\$

I implemented the binary search algorithm. Input vector is sorted by < than operator implemented by type T. The less than operator is expensive so we want to use it as few times as possible.

I would like to know if there are any stupid mistakes, bad practices that I used and how I can improve the code.

template<class T>
long binary_search(const std::vector<T>& v, const T& key){

    if(v.empty()) { return -1; } 

    long lo = 0;
    long hi = v.size() - 1;
    long mid = (long) floor((lo + hi ) / 2); 
    long pmid = -1;  // prev mid 

    while(lo < hi && pmid != mid){

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

        pmid = mid; 
        mid = (long) floor((lo + hi) / 2); 
    }

    if(!(v[mid] < key) && !(key < v[mid])){
        return mid; 
    }

    if(mid - 1 >= 0){
        if( !(v[mid - 1] < key) && !(key < v[mid - 1])){
            return mid - 1; 
        }
    }

    if(mid + 1 <= v.size()){
        if(!( v[mid + 1] < key) && !(key < v[mid + 1] )){
            return mid + 1; 
        }
    }

    return -1; 
}
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

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; 
}
\$\endgroup\$
1
\$\begingroup\$
  • 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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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