Checking an integer's frequency in a sorted array sortedarray array searching noOfComparisons    Posted: 5 years ago Edit answers (1) views (1584)

You are given a sorted array. Write an algorithm to check whether a given integer's frequency is greater than ($$\frac{n}{2}$$). (n is the number of integers in the array).

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit We can use binary search. The algorithm works as : Find the index of the array where the given integer appears first time using binary search. Check whether the given integer is repeated in the next $$\frac{n}{2}$$ indices of the array. Time complexity = $$O(logn)$$. public boolean findIntN/2Times(int[] array, int i){ /* Array length */ int n = array.length; /* Find the index where int i appears first by binary search */ int x = binarySearch(array, 0, n-1, i); /* If int i is not present */ if(x == -1) return false; /* Check if int i's frequency is greater than n/2 */ if((x+n/2) < = (n-1) & & array[x+n/2] == i) return true; else return false; } public int binarySearch(int[] array, int l, int h, int n){ if(h >= l) return -1; /* Middle element */ int m = (l+h)/2; /* Search in the first part */ if(array[m] > n) return binarySearch(array, l, m-1, n); elseif(array[m] < n) return binarySearch(array, m+1, h, n); else return m; }