$0\mathrm{.}1$ Divide$-$and$-$Conquer Practice $(50$ points$)$

Assume you have an array $A[1..n]$ of $n$ elements. A majority element of $A$ is any element occurring

in more than $\frac{n}{2}$ positions $($so if $n=8$ any majority element will occur in at least $5$ positions$).$ Assume

that elements cannot be ordered or sorted, but can be compared for equality. $($You might think of the

elements as chips, and there is a tester that can be used to determine whether or not two chips are

identical.$)$

Design an efficient divide and conquer algorithm to find a majority element in $A($or determine that

no majority element exists$).$ To simplify the solution, you can assume $n$ is a power of two. Aim for

an algorithm that does $O(nlogn)$ equality comparisons between the elements. Include the algorithm

analysis. A more difficult $O(n)$ algorithm is possible, but may be difficult to find.