title: Divide-and-conquer algorithm for finding the majority element?
body: <p>An array is said to have a majority element if more than half of its elements are the same. Is there a divide-and-conquer algorithm for determining if an array has a majority element?</p>
  
  <p>I normally do the following, but it is not using divide-and-conquer. I do not want to use the <a href="http://en.wikipedia.org/wiki/Boyer-Moore_Majority_Vote_Algorithm" rel="noreferrer">Boyer-Moore</a> algorithm.</p>
  
  <pre><code>int find(int[] arr, int size) {
      int count = 0, i, mElement;
  
      for (i = 0; i &lt; size; i++) {
          if (count == 0) mElement = arr[i];
  
          if (arr[i] == mElement) count++;
          else count--;
      }
  
      count = 0;
      for (i = 0; i &lt; size; i++) {
          if (arr[i] == mElement) count++;
      }
  
      if (count &gt; size / 2) return mElement;
      return -1;
  }
  </code></pre>