Find popular items

Find popular item in sorted array of natural numbers.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.

This is actually a very interesting problem. Since the popular item is defined as the element is repeated more than 1 / 4 times, and since it is a sorted array, so it can only occurs on 0, n / 4, n /2 and 3n/4 index. And the rest is just do binary search and get the range.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

public class PopularNumber {  public static void popular(int[] n){   if(n == null || n.length == 0)    return;   int len = n.length;   int[] check = {0, len / 4, len / 2, 3 * len / 4};   for(int i = 0; i < 4; i++){    if(i > 0 && n[check[i]] == n[check[i - 1]])     continue;    int l = check[i];    int start = binarySearchStart(n, n[l]);    int end = binarySearchEnd(n, n[l]);    //need to be larger than the ceil in case len / 4.0 is not an integer    if(end - start + 1 >= Math.ceil(len / 4.0))     System.out.println(n[l]);   }  }  private static int binarySearchEnd(int[] n, int target){   int len = n.length;   int start = 0;   int end = len - 1;   while(start + 1 < end){    int mid = (start + end) / 2;    if(n[mid] <= target)     start = mid;    else     end = mid;   }   if(n[end] == target)    return end;   else return start;  }  private static int binarySearchStart(int[] n, int target){   int len = n.length;   int start = 0;   int end = len - 1;   while(start + 1 < end){    int mid = (start + end) / 2;    if(n[mid] >= target)     end = mid;    else     start = mid;   }   if(n[start] == target)    return start;   else    return end;  }    public static void main(String[] args) {   //int[] n = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8};   int[] n = {1, 1, 2, 3, 4};   popular(n);  } }