c++ - 在O(lg n)领带复杂度的排序数组中找到多数元素

我正在解决这个问题，并且在看一些帖子时，我使用摩尔的投票算法获得了时间复杂度为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 ;
    }

最佳答案

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

如果对数组排序，则多数值可以是中间值。为了验证这一点，让 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");
}