Majority Element in a Sorted Array

Write an algorithm to find if a given integer x appears more than n/2 times in a sorted array of n integers. See this for a similar problem on Majority Element.

Approach: Use binary search to find the first occurrence of x in the array.
TC  = O(log(n)) 

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

#include <iostream> #include <cmath> using namespace std; int binsrch(int *arr, int x, int low, int high){ if(low <= high){ int mid = (low + high) / 2; // returns the first occurrence of x if(arr[mid] == x && (arr[mid] > arr[mid - 1] || mid == 0)){ return mid; } if(x > arr[mid]){ return binsrch(arr, x, mid + 1, high); } else{ return binsrch(arr, x, low, mid - 1); } } return -1; } int isMajority(int *arr, int x, int n){ int first = binsrch(arr, x, 0, n - 1); if(first == -1){ return 0; } if((first + n/2) <= (n - 1) && arr[first + n/2] == x){ return 1; } return 0; } using namespace std; int main(){ int arr[] ={1, 2, 3, 4, 4, 4, 4}; int n = sizeof(arr)/sizeof(arr[0]); int x = 4; if(isMajority(arr, x, n)){ cout << x << " is the majority element." << endl; } else{ cout << x << " is not the majority element." << endl; } return 0; }

Read More

Majority Element

Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Idea : To find the majority element using Moore's Voting Algorithm

Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

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

#include<iostream> using namespace std; int main(){ int arr[] = {2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 2, 4, 4}; //{1, 2, 4, 4, 10, -8}; int n = sizeof(arr)/sizeof(arr[0]); int count, majorityElt; majorityElt = arr[0]; count = 1; for(int i = 1 ; i < n ; i++ ){ if(arr[i] == majorityElt){ count++; } else { count--; } if(count == 0){ count = 1; majorityElt = arr[i]; } } count = 0; for(int i = 0 ; i < n ; i++){ if(arr[i] == majorityElt){ count++; } } if(count > n/2){ cout << majorityElt << " is the majority element " << endl; } else{ cout << "No such element exists" << endl; } return 0; }

Read More