An array A is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an ecient algorithm to tell whether the array has a majority element, and if so, to nd that element. The elements of the array are not necessarily from an ordered domain like the integers, and so there can be no comparison operations. (For example, the array elements may be GIF les.) However you can answer questions of the form: \Is A[i]