O（lg n）tieの複雑さでソートされた配列のマジリティ要素を見つけよう

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）ではありません。バイナリ検索のアイデアは、コードが実行していない時間ごとに検索スペースを半減させることです。

配列が順序付けされている場合は、大部分の値が中間値になります。これを確認するには、を中間値とします。

差が配列のサイズの半分よりも大きい場合半ばチェックの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"); 
}