binary search with vectors in c++

Question

im writing a binary search method for a university assignment, and although i feel like this is the correct way of doing it, I feel like the run time is longer then it should be.. does anyone see any mistakes in this? iterator is a custom class, nothing fancy, does what you would expect it to. vec is a vector of iterators, that point to a bigger linked list of what im "really" searching for

iterator searchVec(const I& item)
{
    int left = 0;
    int right = (int)vec.size()-1;
    int mid = (right+left)/2;

    while(*vec.at(left) != *vec.at(right)){
        mid = (right+left)/2;
        if (mid == 0 || mid == vec.size()-1){
            //nothign else to search, we didnt find anything
            return *vec.end();
        }
        if (*vec.at(mid) == item){
            return vec.at(mid);
        }
        else if (item > *vec.at(mid)){
            left = mid;
        }
        else if (item < *vec.at(mid)){
            right = mid;
        }
    }
    return vec.at(mid);
}

You cannot dereference `vec.end()`. Nor should you, since you want to return an *iterator*, not a value. — Kerrek SB, Mar 30 '13 at 19:15
great point, I modified it to `return vec.at(vec.size()-1);` — Gagan Singh, Mar 30 '13 at 19:17
To state the obvious, you're sure your vector is sorted (and that the sort uses the comparison on the derefenced values), right? Also, you will never find an item that is pointed to by the first or last iterator because you test `if (mid == 0 || mid == vec.size()-1)` before `if (*vec.at(mid) == item)`. You don't need that first check, you should remove it. — jerry, Mar 30 '13 at 19:29
Then what if the vector is empty? No, returning an iterator is generally a good idea, you just have to get all the details right. — Kerrek SB, Mar 30 '13 at 19:33
vector.at() does not return an iterator. Why are you dereferencing it? Is this a vector of pointers to type I? — Etherealone, Mar 30 '13 at 19:40
"Is this a vector of pointers to type I?" yes, well rather a vector of iterators that point to type I — Gagan Singh, Mar 30 '13 at 19:50
Now I noticed the questions tells it, sorry. It seems fine to me. You could output information to console before the while ends and see if it dives into wrong parts of the vector. — Etherealone, Mar 30 '13 at 19:55
You can also remove one of your boolean checks. A proper strong-order should be able to do this with two `operator<()` only. `if (a < b) ... else if (b < a) .... else they're equal` thereby only requiring the single is-less-than operator for the underlying type, and no greater-than or equality operators at all. — WhozCraig, Mar 31 '13 at 05:10

score 0 · Answer 1 · edited May 23 '17 at 11:49

Some thoughts:

You are using std::vector::at which is slow compared to std::vector::operator[].
You cannot dereference vec.end(). Usually, it is returned if you want to signal the caller that no item was found. But here, as you do not return an iterator of vec, maybe you should signal this with a boolean out parameter or an exception.
The loop condition doesn't look right to me. It seems it should be left <= right instead of *vec[left] != *vec[right]. Then the aim of the loop is to select the item. If we break out of the loop, then no item is found.

The exit condition is useless and will prevent finding first and last element, as stated in the comments.

    if (mid == 0 || mid == vec.size()-1)
        //nothign else to search, we didnt find anything
        return *vec.end();
    }

Here is a slightly corrected code:

iterator searchVec(const I& item)
{
    int left = 0;
    int right = (int)vec.size()-1;
    int mid = (right+left)/2;

    while(left <= right) // corrected condition
    {
        mid = (right+left)/2;
        iterator it = vec[mid]; // avoid recomputing vec[mid]
        if (*it == item) // this can be moved in a else {} statement,
            return it;   // after the else if (no impact on performances I think)
        else if (item > *it)
            left = mid + 1; // you were not strictly decreasing the interval
        else if (item < *it)
            right = mid - 1; // same here
    }
    throw not_found();
}

binary search with vectors in c++

1 Answers1