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

## Description

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element, or false otherwise.

A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.

Example 1:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.


Example 2:

Input: nums = [10,100,101,101], target = 101
Output: false
Explanation: The value 101 appears 2 times and the length of the array is 4.
Thus, 101 is not a majority element because 2 > 4/2 is false.


Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i], target <= 109
• nums is sorted in non-decreasing order.

## Solutions

Solution 1: Binary Search

We notice that the elements in the array $nums$ are non-decreasing, that is, the elements in the array $nums$ are monotonically increasing. Therefore, we can use the method of binary search to find the index $left$ of the first element in the array $nums$ that is greater than or equal to $target$, and the index $right$ of the first element in the array $nums$ that is greater than $target$. If $right - left > \frac{n}{2}$, it means that the number of occurrences of the element $target$ in the array $nums$ exceeds half of the length of the array, so return $true$, otherwise return $false$.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.

Solution 2: Binary Search (Optimized)

In Solution 1, we used binary search twice to find the index $left$ of the first element in the array $nums$ that is greater than or equal to $target$, and the index $right$ of the first element in the array $nums$ that is greater than $target$. However, we can use binary search once to find the index $left$ of the first element in the array $nums$ that is greater than or equal to $target$, and then judge whether $nums[left + \frac{n}{2}]$ is equal to $target$. If they are equal, it means that the number of occurrences of the element $target$ in the array $nums$ exceeds half of the length of the array, so return $true$, otherwise return $false$.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.

• class Solution {
public boolean isMajorityElement(int[] nums, int target) {
int left = search(nums, target);
int right = search(nums, target + 1);
return right - left > nums.length / 2;
}

private int search(int[] nums, int x) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}

• class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
auto left = lower_bound(nums.begin(), nums.end(), target);
auto right = upper_bound(nums.begin(), nums.end(), target);
return right - left > nums.size() / 2;
}
};

• class Solution:
def isMajorityElement(self, nums: List[int], target: int) -> bool:
left = bisect_left(nums, target)
right = bisect_right(nums, target)
return right - left > len(nums) // 2


• func isMajorityElement(nums []int, target int) bool {
left := sort.SearchInts(nums, target)
right := sort.SearchInts(nums, target+1)
return right-left > len(nums)/2
}

• function isMajorityElement(nums: number[], target: number): boolean {
const search = (x: number) => {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
const left = search(target);
const right = search(target + 1);
return right - left > nums.length >> 1;
}