Check If a Number Is Majority Element in a Sorted Array - Solution & Explanation

Problem Overview: You are given a sorted integer array and a target value. The task is to determine whether the target appears more than n / 2 times. Because the array is already sorted, the occurrences of any value are grouped together, which allows efficient searching using binary search instead of scanning the entire array.

Approach 1: Binary Search (O(log n) time, O(1) space)

Use binary search to locate the first occurrence of the target. Once you know where the target begins, compute the index start + n/2. If that index is within bounds and the value at that position is still the target, the element appears more than half the time. The insight comes from the sorted property: if a number is a majority element, the element exactly n/2 positions ahead of its first occurrence must also be the same value. This avoids counting occurrences and leverages the structure of the array.

Approach 2: Binary Search (Optimized) (O(log n) time, O(1) space)

Another approach performs two binary searches to find the leftmost and rightmost occurrences of the target. The difference between these indices gives the total frequency of the element. If right - left + 1 > n/2, the target is the majority element. This technique is a classic pattern for counting duplicates in a sorted array using binary search. While it performs two searches instead of one, the complexity remains logarithmic and the implementation is straightforward to reason about.

Recommended for interviews: The single-search majority check (finding the first occurrence and verifying the n/2 offset) is the most elegant solution. It demonstrates that you understand how sorted order enables positional reasoning instead of brute-force counting. Showing the two-boundary binary search method is also acceptable, but the optimized offset trick usually stands out as the cleanest solution.