在 O(log n) 时间复杂度中查找排序数组中的多数元素

Question

我正在处理这个问题，在查看一些帖子时，我使用摩尔投票算法获得了时间复杂度为 O(n) 的解决方案。众数元素是出现次数大于数组大小除以 2 的元素。对于 o(lg n) 时间，以下是我的代码，请建议它是否在 o(lg n) 中。我对编程很陌生，欢迎提出建议。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std ;

int binarySearch(vector <int> a, int l, int h){

        if(l - h < a.size() / 2)
            return -1;

        int mid = (l+h)/2;
        int temporaryLow = mid;
        int temporaryHigh = mid;

        while(temporaryLow > 0 && a[temporaryLow] == a[mid])
            temporaryLow--;

        while(temporaryHigh < a.size() && a[temporaryHigh] == a[mid])
            temporaryHigh++;

        if((temporaryHigh -1) - (temporaryLow+1) +1 >= a.size()/2){
            return a[mid];
        }else{

            return max(binarySearch(a,0,temporaryLow),binarySearch(a,temporaryHigh,h));

        }
    }

 int findMajority(vector <int> numbers){

        return binarySearch(numbers , 0, numbers.size());
    }


    int main()
    {
        int n ;     
        vector <int> a ;
    while ((cin >> n) && n != 9999)
    a.push_back(n);

        int majority = findMajority(a);
        cout << majority ;
    }

Answer 1

不，这不是 O(log n)。二进制搜索的想法是每次将搜索 space 减少一半，而您的代码没有这样做。

如果数组是有序的，多数值可以是中间值。为了验证这一点，令 mid 为中间值。

找到mid的lower_bound和upper_bound检查差值是否大于数组大小的一半.

代码：

#include <vector>
#include <algorithm>

int majorityElement(const std::vector<int> &array) {
    auto size = array.size();
    if (!size)
        throw std::runtime_error("no majority element");
    auto mid = array[size/2];
    // These run in O(lg N) because array is sorted
    auto low_index = std::lower_bound(array.cbegin(), array.cend(), mid);
    auto upp_index = std::upper_bound(array.cbegin(), array.cend(), mid);
    if ((upp_index - low_index) > size/2) 
        return mid;
    throw std::runtime_error("no majority element");
}

在 O(log n) 时间复杂度中查找排序数组中的多数元素

Find Majority element in a sorted array in O(lg n) tie complexity

c++

arrays

sorting

binary-search