## Searching 53

QUESTION

Write a C program to find if a given integer x appears more than n/2 times in a sorted array of n integers. Take the number of elements, the elements of the array and the integer x as input.\n\nBasically, we need to write a function say isMajority() that takes an array (arr[] ), arrays size (n) and a number to be searched (x) as parameters and returns true if x is a majority element (present more than n/2 times).

“TESTCASE_1”: “7\n1 2 3 3 3 3 10\n3\n###—###SEPERATOR—###—\n3 appears more than 3 times in arr”, “TESTCASE_2”: “5\n1 1 1 2 2\n1\n###—###SEPERATOR—###—\n1 appears more than 2 times in arr”, “TESTCASE_3”: “7\n1 2 3 4 4 4 4\n1\n###—###SEPERATOR—###—\n1 does not appear more than 3 times in arr”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````# include <stdio.h>
# define bool int

bool Morenooftimes(int array[], int n, int x)
{
int i;
int final_index = n % 2 ? n / 2 : (n / 2 + 1);

for (i = 0; i < final_index; i++)
{
/* check if x is presents more than n/2 times */
if (array[i] == x && array[i + n / 2] == x)
return 1;
}
return 0;
}

int main()
{
int n,i,x;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
scanf("%d",&x);
if (Morenooftimes(arr, n, x))
printf("%d appears more than %d times in arr", x, n/2);
else
printf("%d does not appear more than %d times in arr", x, n/2);

return 0;
}``````