title: Linear Time Voting Algorithm. I don't get it
body: <p>As I was reading this (<a href="https://stackoverflow.com/questions/278488/puzzle-find-the-most-common-entry-in-an-array">Find the most common entry in an array</a>), the <a href="http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html" rel="nofollow noreferrer">Boyer and Moore's Linear Time Voting Algorithm</a> was suggested.  </p>
  
  <p>If you follow the link to the site, there is a step by step explanation of how the algorithm works. For the given sequence, <code>AAACCBBCCCBCC</code> it presents the right solution.</p>
  
  <blockquote>
    <p>When we move the pointer forward over
    an element e:    </p>
    
    <ul>
    <li>If the counter is 0, we set the current candidate to e and we set the
    counter to 1.</li>
    <li>If the counter is not 0, we increment or decrement the counter
    according to whether e is the current
    candidate. </li>
    </ul>
    
    <p>When we are done, the current
    candidate is the majority element, if
    there is a majority.</p>
  </blockquote>
  
  <p>If I use this algorithm on a piece of paper with <code>AAACCBB</code> as input, <strong>the suggested candidate would become B</strong> what is obviously wrong.  </p>
  
  <p>As I see it, there are two possibilities</p>
  
  <ol>
  <li>The authors have never tried their algorithm on anything else than <code>AAACCBBCCCBCC</code>, are completely incompetent and should be fired on the spot <em>(doubtfull)</em>.</li>
  <li><strong>I am clearly missing something</strong>, must get banned from Stackoverflow and never be allowed again to touch anything involving logic.</li>
  </ol>
  
  <p>Note: Here is a a <a href="http://www.cis.rit.edu/~njs8030/coding/majority.C" rel="nofollow noreferrer">C++ implementation of the algorithm</a> from Niek Sanders. I believe he correctly implemented the idea and as such it has the same problem (or doesn't it?).</p>