Problems understanding the workings behind C++ Algorithm Binary Search

Question

I was looking through the list of algorithms and decided to have a look at the find method

Find Method

template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

It seems Find has a running time of Big O (n) as it iterates through every element in the container to find the value.

My thoughts immediately thought of Binary Search and I went to have a look at it .

Binary Search

template <class ForwardIterator, class T>
  bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = std::lower_bound(first,last,val);
  return (first!=last && !(val<*first));
}

Knowing that it utilises another function : lower bound , I went on to research lower bound which returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

This is my analysis

Assuming an array data structure

[ 1 , 4 , 7 , 10 , 12 ]

If we use binary search to search for 6 , first would be equal to an iterator pointing to 7

*first would be of value 1 , val would be of value 6 then !(val<*first) would be true

Since first!=last == true && !(val<*first) == true , the binary search function would return true even though 6 does not exist in the array

I know there is flaw in my reasoning , can someone explain to me where did i go wrong ???

Answer 1

*first would be of value 1

There's your problem. first is an iterator to the element with value 7, so *first is 7. That makes !(val<*first) become !(6<7) which is false.