# 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.

Example:

input:nums=[2,4,5,5,5,5,5,6,6], target=5return True

Approach 1:

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)

Space O(1)

Approach 2:

Binary Search

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

low=0

high=len(nums-1)

n=len(nums)//2

while(low<high):

mid=(low+high)/2

if(nums[left]<target):

low=mid+1

else:

high=midreturn (low + n/2<len(nums) and nums[low + n/2]==target)

Time : O(log(n))

Space O(1)

Approach 3:

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.

return nums[len(nums)//2]

Time: O(1)

Space : O(1)