The minimum number of comparisons required to determine if an integer appears…

Concept: In a sorted array, if a value occurs more than n/2 times, its run of occurrences must cover the middle index ⌊n/2⌋ (0-indexed), so the value stored at arr[⌊n/2⌋] is the only integer that can possibly be a majority value. Also, all occurrences of any value in a sorted array form one contiguous block, so this candidate's count equals (last index − first index + 1) of its block. Locating each boundary of that block by binary search costs Θ(log n) in the worst case, and no comparison-based search over an n-element sorted range can beat Θ(log n) (each comparison can at best halve the remaining range), so the algorithm's cost and the lower bound match at Θ(log n).

1. Because the array is sorted, if the target value occurs more than n/2 times its run of occurrences must cover the middle index ⌊n/2⌋, so the only candidate for a majority value is the value stored at arr[⌊n/2⌋] — read this value first, in O(1).

2. All occurrences of that candidate value sit together in one contiguous run, since the array is sorted.

3. Binary search locates the first index i of that run in O(log n) comparisons.

4. Binary search locates the last index j of that run in O(log n) comparisons.

5. The frequency of the candidate value is then (j − i + 1), computed in O(1) once i and j are known; more than n/2 occurrences confirms a majority.

6. Total work = O(1) + O(log n) + O(log n) + O(1) = Θ(log n) — and since no comparison can shrink the search range by more than half, Θ(log n) is also the best possible, so this matches the lower bound too.

Cross-check: for {1, 1, 2, 2, 2, 2, 3, 3} (n = 8), the first and last occurrence of 2 are each found in about log2 (8) = 3 comparisons per side — a small constant multiple of log n, not a linear O(n) scan. For {1, 2, 2, 2, 4, 4}, inspecting only the middle position is not enough to certify a majority count; the two binary searches for the run's boundaries are still required, ruling out a constant-time check.