Check If a Number Is Majority Element in a Sorted Array

Problem Statement

The problem requires determining if a given integer target is the majority element in a given sorted array nums. A majority element is defined as an element that appears more than half the number of times in the list, that is, more than nums.length / 2 times. The objective is to return more true if the target is a majority element, otherwise return false.

Examples

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.

Approach and Intuition

To determine if target is a majority element in nums, consider the following steps:

1. Calculate the required count for the majority, which is more than nums.length / 2.
2. Since the array is sorted, binary search can be efficiently used to find the first and last occurrence of target in nums, which will help in determining the total number of times target appears in the array.
3. Check if the count of target surpasses the majority count calculated in step 1. If it does, return true; else, return false.

From the examples:

• In Example 1, target is 5, and it appears 5 times in nums, which is more than 9/2, thus 5 is a majority element.
• In Example 2, target is 101, appearing only 2 times in nums. Since 2 is not more than 4/2, 101 is not a majority element.

Constraints Analysis

• The constraints ensure that even a straightforward approach that involves counting the number of times target appears will be within acceptable performance limits.
• The sorted nature of nums provides a crucial insight that optimized searching techniques like binary search can be directly applied.

By taking advantage of the array's sorted property, effective search algorithms can significantly prune down the search space, making the solution both efficient and easy to understand.

Solutions

class Solution {
public:
    int find_lower_bound(vector<int>& arr, int val) {
        int left = 0;
        int right = arr.size() - 1;
        int pos = arr.size();
            
        while (left <= right) {
            int middle = (left + right) / 2;
                
            if (arr[middle] >= val) {
                right = middle - 1;
                pos = middle;
            } else {
                left = middle + 1;
            }
        }
            
        return pos;
    }
        
    bool checkMajorityElement(vector<int>& arr, int val) {
        int firstPos = find_lower_bound(arr, val);
            
        return (firstPos + arr.size() / 2 < arr.size()) && (arr[firstPos + arr.size() / 2] == val);
    }
};