Question

The minimum required number of comparison required to determined if an integer appears more than n/2 times in a sorted array of n integers is

• A. $\ominus$(n)
• B. $\ominus$(log n)
• C. $\ominus$($lo{g}^2$n)
• D. $\ominus$(1)

Answer 1

The correct option is B $\ominus$(log n)

Consider any array of n elements which stored integers in sorted order, A[1], A[2],...A[n]. If we want to search an element x with the help of binary search then in expected case comparison is not greater than $\lceil$log(n + 1)$\rceil$. But if integral appears n/2 times in an array and array already sorted then it take $\ominus$(1) times for consecutive locations. So total no. of comparison is not greater than $\ominus$(log n) time.