The minimum number of comparisons required to determine if an integer appears…
2008
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
- A.
Θ(n)
- B.
Θ(logn)
- C.
Θ(n*logn)
- D.
Θ(1)
Attempted by 126 students.
Show answer & explanation
Correct answer: B
Key idea: any value that appears more than n/2 times in a sorted array must occupy the middle position.
Pick candidate = arr[floor(n/2)].
Use binary search to find the first occurrence (lower bound) index of the candidate.
Use binary search to find the last occurrence (upper bound) index of the candidate (or find lower bound of candidate+1 and subtract one).
Compute count = last_index - first_index + 1. If count > n/2, the element appears more than n/2 times; otherwise it does not.
Complexity: each binary search takes Θ(log n) comparisons, so the total is Θ(log n). This is asymptotically optimal for locating boundaries in a sorted array.
A video solution is available for this question — log in and enroll to watch it.