問題的理解背後的C++算法二進制搜索運作

我一直在尋找通過的algorithms列表，並決定去看看find方法問題的理解背後的C++算法二進制搜索運作

查找方法

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

看來查找運行時間爲Big 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，我繼續研究下界這返回指向範圍爲[第一的第一個元素的迭代器，最後），這不比val小。

這是我的分析

假設一個陣列

[1,4，7，10，12]

如果我們使用二進制搜索來搜索6，first將等於一個迭代器指向7

*first將是值1，val將是值6然後 !(val<*first)將是真實的

由於first!=last ==真& & !(val<*first) ==真，即使6不數組中存在

我知道有缺陷的二進制搜索功能將返回true。我的推理，可以有人向我解釋，我在哪裏出錯？

來源

2014-02-09 Computernerd

如果'first'是一個指向7的迭代器，那麼'* first'似乎不太可能是值1 ...... –

'首先會等於指向7'的迭代器，而'* first將會是價值'是不相容的陳述。選擇一個你認爲是真實的，並從那裏繼續。 –

假設我查找了7而不是6，*首先是10因此！（val <* first）將是錯誤的，並且二進制搜索將返回false，儘管7存在於數組中，這個推理有什麼錯誤 – Computernerd

*first很有價值1

有你的問題。 first是值爲7的元素的迭代器，因此*first爲7.這使得!(val<*first)變爲!(6<7)，即false。

來源

2014-02-09 10:27:28

假設我查找了7而不是6，*首先是10因此！（val <* first）將是錯誤的，並且二進制搜索將返回false，儘管7存在於數組中，這個推理有什麼錯誤 - Computernerd 8分鐘前 – Computernerd

@Computernerd事實並非如此。 'lower_bound'找到*值不低於您要查找的值的第一個值。所以它會發現'7'。 –

問題在於，爲了實際*查找*值（而不是限制它），函數將不得不採用比較運算符*和*相等比較運算符。 STL的設計理念是通用性和性能。使用'lower_bound'並且在你自己的函數中測試相等性沒有性能成本。有些事情不是平等可比的。 – Ben

問題的理解背後的C++算法二進制搜索運作

回答

相關問題