1102. Check If a Number Is Majority Element in a Sorted Array

• Difficulty: Easy

• Topics: Array, Binary Search

• Similar Questions:

  • Majority Element

  • Majority Element II

Problem:

Given an array nums sorted in non-decreasing order, and a number target, return True if and only if target is a majority element.

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

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.

Note:

1. 1 <= nums.length <= 1000
2. 1 <= nums[i] <= 10^9
3. 1 <= target <= 10^9

Solutions:

class Solution {
public:
    bool isMajorityElement(vector<int>& nums, int target) {
        if (nums.size() == 0)   return false;
        int l1 = 0;
        int l2 = 0;
        int r1 = nums.size() - 1;
        int r2 = nums.size() - 1;

        while (true) {   
            if (l1 <= r1) {
                int mid = l1 + (r1 - l1) / 2;
                if (nums[mid] >= target) {
                    r1 = mid;
                } else {
                    l1 = mid + 1;
                }
            }

            if (l1 > r1)    return false;

            if (l2 <= r2) {
                int mid = r2 - (r2 - l2) / 2;
                if (nums[mid] <= target) {
                    l2 = mid;
                } else {
                    r2 = mid - 1;
                }
            }
            if (l2 > r2)    return false;

            if (l2 - r1 + 1 > int(nums.size() / 2)) { // trap! 
                return true;
            }
            if (r2 - l1 + 1 <= int(nums.size() / 2)) { // trap!
                return false;
            }
        }
    }
};