GATE | GATE CS 2008 |问题40

确定一个整数在n个整数的排序数组中的出现次数是否超过n/2次所需的最小比较次数为

（A） Θ（n） （B） Θ（logn） （C） Θ（对数*n） （D） Θ(1) 答复: （B） 说明： 如果你回答了θ（1），那么想想例子{1,2,2,4,4}，{1,1,2,2,2,2,3}

找出一个整数在n个整数的排序数组（升序）中是否出现超过n/2次的最佳方法是二进制搜索方法。

1. 元素的第一次出现可以使用分治技术在O（log（n））时间内发现，假设它是i。
2. 使用分治技术可以在O（log（n））时间内找到元素的最后一次出现，假设它是j。
3. 现在该元素的发生数（count）是（j-i+1）。总体时间复杂度=logn+logn+1=O（logn）

看见 检查排序数组中的多数元素

这个解决方案是由 尼马尔·巴拉德瓦伊 这个问题的小测验