1150. Check If a Number Is Majority Element in a Sorted Array

Brute Force

class Solution:
    def isMajorityElement(self, A: List[int], target: int) -> bool:
        n = len(A)
        cnt = 0
        for a in A:
            if a == target:
                cnt += 1
            elif a > target:
                return cnt > n//2
        return cnt > n//2

Binary Search Optimal Solution there are three cases where a majority number will locate in a sorted array. (1) in the beginning (2) in the middle (3) in the end However, one commen feature is: Array[mid] will alwayse be majority number since its amount > n//2

Then we can use bisect to get first target number and last target number

class Solution:
    def isMajorityElement(self, A: List[int], target: int) -> bool:
        n = len(A)
        if A[n//2] != target:
            return False 
        k = n//2
        lo = bisect.bisect_left(A,target)
        hi = lo + k
        if hi < n and A[hi] == target :
            return True
        return False 

self-defined Helpfer function version

class Solution:
    def isMajorityElement(self, A: List[int], target: int) -> bool:
        n = len(A)
        if A[n//2] != target:
            return False 
        k = n//2
        def helper(lo,hi,target):
            while lo < hi:
                mid = lo + (hi-lo)//2
                if A[mid] < target:
                    lo = mid + 1 
                else:
                    hi = mid # find the first position at target 
            return lo
        k = helper(0,n,target+1)-helper(0,n,target) 
        if k > n//2:
            return True
        return False 