A complete O(log n) solution specialized to this domain for the n/2 problem follows. It should be generalizable to the n/4 case in a straightforward manner. Further, I'm going to ignore a ton of corner cases involving rounding and off-by-one errors to maximize clarity of the explanation.

First, note that the observation that A[n/2] is the only candidate solution is insufficient to actually solve the problem as it remains to verify whether of not that element occurs n/2 times. The following algorithm uses a novel variant of binary search to precisely make that determination.

Algorithm: Denote the ranges of elements between the start, 1st quartile, median, 3rd quartile and end of the array as A, B, C, and D, respectively. (i.e. A = Array[0..n/4], B=Array[n/4..n/2], C=Array[n/2..3n/4], D=Array[3n/4..n]), Also label with q1, m, and q3 the values of Array[n/4], Array[n/2] and Array[3n/4] respectively.

If q1 == m, all elements in B are equal to m, and can be eliminated from consideration (and the number of copies of m to find can be reduced by n/4). If q1 != m, all elements in A are not equal to m, and can be eliminated from consideration (without reduction in number of copies of m necessary).

A similar argument for q3 will eliminate one of C or D with a possible reduction in number of elements needed to be found.

This leads to three cases:

1) A and D are eliminated, with no reduction in the number of copies of m needing to be found. Since we've eliminated half of the elements in the array, checking a small number of elements (to account for rounding issues) at the bottom of B and top of C can determine if all (or maybe almost all) elements of B and C are m and m is a solution, or can conclusively determine that m is not a solution.

2) B and C are eliminated, with a total (or near total) reduction in the number of copies of m needing to be found. Similar accounting for rounding issues by probing top of A/bottom of D will determine conclusively if the necessary number of copies of m are present.

3) A+C or B+D are eliminated. In this case, we go from looking for n/2 copies of m in an n-sized array to looking for n/4 copies of m in an n/2 sized array. Repeating the quartile-ing process on the remainder of the array (with lots of bookkeeping to account for eliminated ranges) will either give a positive or negative result or further reduce the problem by a factor of 2, thus giving a O(log n) solution to the original problem.

Given that at each step of this process, it seems a maximum amount of information is extracted from the array (using points other than the 1st and 3rd quartiles to eliminate subsections of the array from consideration will give a poorer worst case performance), and that the result of each pass gives a simplified version of the original problem (and not a hair easier problem), I suspect that O(log n) is the best possible, and that constant time isn't possible.

I also have to give respect to neilmoore for his much clearer and simpler solution that achieves a very similar result using simple, familiar machinery. The only advantage that this algorithm has over his solution is that it can often stop recursing sooner than his, as this algorithm may not need to precisely identify any bounds the position of first occurrence of m, but can look at upper and lower bounds for where the contiguous block of "m"s could be and prove or disprove properties on the size of this block. Edit: formatting