This method was proposed by someone to find majority element in the array.I can't really understand how things are going on.Can anyone explain this to me.
Regards.
Let f(i, j) be the majority of elements from i-th to j-th in nums
By the definition of majority it is the number of elements that appears more than half of the total numbers in the array,
Assume that all the rest elements in nums from i-th to j-th except those two numbers above are the same,
then they will appear less than (mid-i+1)/2 + (j-mid)/2 = (j-i+1)/2 times from i-th to j-th in nums
Therefore any elements except those two numbers above cannot be the majority of elements in nums;
hence f(i,j) = f(i,mid) or f(mid+1,j)