设计递归算法

Question

题目：若数组A中，有一半以上的元素相同，设计一个递归算法，以O(n)时间找到这个元素

Answer 1

基本思想是先用必要条件找，然后再遍历一遍验证是否满足条件，不用递归很容易。
因为你限制了要用递归，那么看上去只能这样了：
若a在A中占据一半以上，那么把A分成A1，A2两部分之后，a在其中至少一个子列中也占据一半以上。
利用这一性质，递归地在A1,A2中寻找候选元素，然后遍历数组以验证这两个候选元素(如果存在的话)是否满足条件。
根据归纳假设，在A1,A2中寻找候选元素的时间复杂度是O(n)，再对A遍历至多两遍，复杂度仍然是O(n)。