text: 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
code: def _binarySearch ( arr , low , high , x ) : NEW_LINE INDENT if high >= low : NEW_LINE INDENT mid = ( low + high ) // 2 NEW_LINE if ( mid == 0 or x > arr [ mid - 1 ] ) and ( arr [ mid ] == x ) : NEW_LINE INDENT return mid NEW_LINE DEDENT elif x > arr [ mid ] : NEW_LINE INDENT return _binarySearch ( arr , ( mid + 1 ) , high , x ) NEW_LINE DEDENT else : NEW_LINE INDENT return _binarySearch ( arr , low , ( mid - 1 ) , x ) NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT def isMajority ( arr , n , x ) : NEW_LINE INDENT i = _binarySearch ( arr , 0 , n - 1 , x ) NEW_LINE if i == - 1 : NEW_LINE INDENT return False NEW_LINE DEDENT if ( ( i + n // 2 ) <= ( n - 1 ) ) and arr [ i + n // 2 ] == x : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT