c++ - 理解 C++ 算法二进制搜索背后的工作原理的问题

Question

我正在查看 algorithms 的列表并决定看看 find方法

查找方法

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;
}

Find 似乎有一个大 O(n) 的运行时间，因为它遍历容器中的每个元素以查找值。

我的思绪立刻想到了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));
}

知道它利用了另一个函数:lower bound ，我继续研究下界，它返回一个迭代器，指向 [first,last) 范围内的第一个元素，它不小于 val。

这是我的分析

假设一个数组数据结构

[ 1 , 4 , 7 , 10 , 12 ]

如果我们使用二进制搜索来搜索 6 , first将等于指向 7 的迭代器

*first将是值(value) 1 ， val将是值 6 然后 !(val<*first)会是真的

自 first!=last == 真 && !(val<*first) == 真 ，即使数组中不存在 6，二分搜索函数也会返回 true

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

这是你的问题。 first是指向值为 7 的元素的迭代器，所以 *first是 7。这使得 !(val<*first)成为!(6<7)这是 false .