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

user_6001968 0
Viewed 807

I am working with this problem and while looking at some of posts I went got a solution with time complexity O(n) using Moore's voting algorithm . Majority element is that element which occurs more than size of array divided by 2 . For o(lg n) time following is my code please suggest whether it is in o(lg n). I welcome suggestions as I am very new to programming .

#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 ;
    }
binary-search sorting arrays c++
1 Answers

No, it is not O(log n). Idea of binary search is to reduce the search space by half each time, which your code is not doing.

If array is ordered, majority value could be the middle value. To verify this, let mid be the middle value.

Find the lower_bound and upper_bound of mid check if difference is greater than half of array size.

code :

#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");
}
user_73148710
Related