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

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 Answers

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;
}

You need to Sign In to post your solution.