HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Binary search feedback and improvements

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
searchbinaryandfeedbackimprovements

Problem

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
long binary_search(const std::vector& 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 = 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; 
}

Solution

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
long binary_search(const std::vector& 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; 
}

Code Snippets

mid = lo + (hi - lo) / 2;
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; 
}

Context

StackExchange Code Review Q#93284, answer score: 2

Revisions (0)

No revisions yet.