Find maximum in array without comparisons between elements Suppose $A$ is an array of integers, $|A|=n$, $A=\{a_i|1\leq a_i\leq N, i=1\ldots n\}$. 

The goal is to find an efficient algorithm $\cal{F}$ to find maximum element in $A$ with these restrictions: 


$\cal{F}$ should not compare any $a_i$ with any $a_j$ ever. 
$\cal{F}$ also should not add, subtract or exploit some fancy facts about integers
$\cal{F}$ may, however, compare any $a_i$ with some predetermined constant number, and this number may depend on $N$


Why does algorithm exist? Well, counting sort will work, it never compares elements with each other. Its complexity is $O(n+N)$.

I propose this:

compare all $a_i$ with $N/2$, let $L=\{a_i\in A|a_i&lt;\frac{N}{2}\}$, $U=\{a_i\in A|a_i\geq\frac{N}{2}\}$. 

If $U$ isn't empty, we may throw $L$ away and compare $U$ with $3N/4$, etc...

If $U$ is empty, we have our initial problem but now the upper bound is $N/2$. Call algorithm recursively.

Basically, it is binary search on $N$, so it will do in $O(n\lceil\log N\rceil)$ in the worst case. If $N$ is big enough it is better than counting sort.

Two questions:

a) am I correct with my algorithm? I can't see any flows in binary search implementation.

b) it is not obvious to me that binary search in this problem is the best solution, is it possible to do better? If not, how to prove it?



I've added some more explanation to clarify the question. According to comments (thanks, EvilJS) I've used term "comparison-based sorting" wrong, so sorry for that.
a) am I correct?


No, that's not correct. Suppose this array is an unsorted array, and you want to find a maximum element in this array. 

First, sorting this array in the increasing order. You can use mergesort or quicksort to sort the array. Mergesort will guarantee the time complexity in the worst and average cases is O(nlogn). However, quicksort will take O(nlogn) for the average case, and O(n) for the worst case. Regarding the worst case of quicksort, if partitioning the array into two groups which one group is empty and another one is (n-1), this will take O(n) time complexity. 

Second, after you have a sorted array in increasing order, you can get the maximum element at the last element in the sorted array.      

b) is it possible to do better?


You can use heapsort with max heaps property. In this case, the largest element is at the root for max heaps. Heapsort will take O(nlogn) since building maxheap takes O(n) and max-heapifying takes O(logn). It takes only O(1) to find a maximum element.