# Check if a number is majority element in the sorted array

1 min readSep 1, 2021

--

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=0high=len(nums-1)n=len(nums)//2while(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)