Check for Majority Element in a sorted array | If x is present in arr [ low ... high ] then returns the index of first occurrence of x , otherwise returns - 1 ; Check if arr [ mid ] is the first occurrence of x . arr [ mid ] is first occurrence if x is one of the following is true : ( i ) mid == 0 and arr [ mid ] = = x ( ii ) arr [ mid - 1 ] < x and arr [ mid ] == x ; This function returns true if the x is present more than n / 2 times in arr [ ] of size n ; Find the index of first occurrence of x in arr [ ] ; If element is not present at all , return false ; check if the element is present more than n / 2 times ; Driver code
function _binarySearch ( arr , low , high , x ) { if ( high >= low ) { let mid = parseInt ( ( low + high ) / 2 , 10 ) ; if ( ( mid == 0 x > arr [ mid - 1 ] ) && ( arr [ mid ] == x ) ) return mid ; else if ( x > arr [ mid ] ) return _binarySearch ( arr , ( mid + 1 ) , high , x ) ; else return _binarySearch ( arr , low , ( mid - 1 ) , x ) ; } return - 1 ; } function isMajority ( arr , n , x ) { let i = _binarySearch ( arr , 0 , n - 1 , x ) ; if ( i == - 1 ) return false ; if ( ( ( i + parseInt ( n / 2 , 10 ) ) <= ( n - 1 ) ) && arr [ i + parseInt ( n / 2 , 10 ) ] == x ) return true ; else return false ; } let arr = [ 1 , 2 , 3 , 3 , 3 , 3 , 10 ] ; let n = arr . length ; let x = 3 ; if ( isMajority ( arr , n , x ) == true ) document . write ( x + " " + parseInt ( n / 2 , 10 ) + " " ) ; else document . write ( x + " " + parseInt ( n / 2 , 10 ) + " " ) ;