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. | Θ(log*n) |
| D. | Θ(1) |
Answer : B Explanation : Since it is a sorted array, we can use binary search to identify the position of the first occurence of the given integer in (logn) steps. If at all this integer repeats, its appearance has to be continuous because the array is sorted. Vishal_Gupta said: (9:59pm on Thursday 26th November 2015)
Since array is sorted so only two comparison are enough to know that an integer appears more than n/2 times correct option is D
|
|
|
Option: A Explanation : Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. Explanation will come here. |
