everyone is posting moore's voting solution which is very nice. but if the input array is sorted we can do it in O(lgn) time. sometimes the interviewer may expect this solution rather than moore's voting.

```
public class Solution {
public List<Integer> majorityElement(int[] nums) {
if(nums.length == 0) return new LinkedList<>();
List<Integer> ans = new LinkedList<>();
Arrays.sort(nums);
int cand1 = nums[nums.length/3];
int cand2 = nums[2*nums.length/3];
if(cand1 == cand2){
ans.add(cand1);
return ans;
}
int len1 = binarySearch(nums, false, cand1) - binarySearch(nums, true, cand1)+1;
if(len1 > nums.length/3) ans.add(cand1);
int len2 = binarySearch(nums, false, cand2) - binarySearch(nums, true, cand2)+1;
if(len2 > nums.length/3) ans.add(cand2);
return ans;
}
int binarySearch(int[] nums, boolean op, int target){
int ans = 0;
int left = 0, right = nums.length-1;
while(left <= right){
int mid = left + (right-left)/2;
if(nums[mid] == target){
ans = mid;
if(op){
right = mid-1;
}else{
left = mid+1;
}
}else if(nums[mid] < target){
left = mid+1;
}else{
right = mid-1;
}
}
return ans;
}
}
```