Check If a Number Is Majority Element in a Sorted Array
Problem
Given an integer array nums sorted in non-decreasing order and a number target, return true if target is a majority element, and false otherwise. A majority element is an element that appears more than nums.length / 2 times in the array.
nums = [2, 4, 5, 5, 5, 5, 5, 6, 6], target = 5truedef is_majority_element(nums, target):
n = len(nums)
lo = bisect_left(nums, target)
if lo == n or nums[lo] != target:
return False
return lo + n // 2 < n and nums[lo + n // 2] == targetfunction isMajorityElement(nums, target) {
const n = nums.length;
const lo = lowerBound(nums, target);
if (lo === n || nums[lo] !== target) return false;
const mid = lo + ((n / 2) | 0);
return mid < n && nums[mid] === target;
}class Solution {
public boolean isMajorityElement(int[] nums, int target) {
int n = nums.length;
int lo = lowerBound(nums, target);
if (lo == n || nums[lo] != target) return false;
int mid = lo + n / 2;
return mid < n && nums[mid] == target;
}
}bool isMajorityElement(vector<int>& nums, int target) {
int n = nums.size();
int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (lo == n || nums[lo] != target) return false;
int mid = lo + n / 2;
return mid < n && nums[mid] == target;
}Explanation
A majority element appears more than half the time. Since the array is sorted, all copies of target sit together in one solid block — and we can confirm majority with two cheap binary search ideas instead of counting everything.
First we use bisect_left (a binary search) to find lo, the leftmost index where target could go. If lo is past the end or nums[lo] isn't target, the value isn't present at all, so we return False.
Now the clever check: if target truly fills more than half the array, then starting at its first occurrence lo and stepping forward by n // 2 positions must still land inside that block. So we test nums[lo + n // 2] == target.
Why this works: more than n/2 equal values form a run longer than half the array; any window of length n/2 starting at the run's left edge stays inside it. If the value at that probe differs, the run is too short.
Example: nums = [2, 4, 5, 5, 5, 5, 5, 6, 6], target = 5, n = 9. Leftmost 5 is at index 2; probe 2 + 4 = 6 and nums[6] = 5 matches, so it is a majority — True — all in O(log n).