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