Check if a number is majority element in the sorted array
Given an array in non decreasing order. Given a target, check if the occurence of target is atleast n/2 times. Return true in that case, else return false. presence of majority element is confirmed in the array.
input:nums=[2,4,5,5,5,5,5,6,6], target=5return True
Iterate through the array. For first occurence of target say at index ‘i’ see whether the character at i+(n/2) is also target character. Then return True
Time : O(n)
Since the array is sorted , use binary search.
Using binary search we find first occurence of target(at end of binary search low is at this position). Then check if this index position +n/2 is also target
high=midreturn (low + n/2<len(nums) and nums[low + n/2]==target)
Time : O(log(n))
Since the array is sorted, and the presence of the majority element in the array is confirmed , therefore the mid index basically will contain the majority element.
Space : O(1)