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 ???
firstis an iterator pointing to 7, then it seems unlikely that*firstwould be of value 1...first would be equal to an iterator pointing to 7and*first would be of valueare incompatible statements. Pick one you think is true and continue from there.*firstwould be 7, because 7 is the first element not less than 7.