BoyerMoore.cs

usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;

namespaceAlgorithms.Search;

/// <summary>
/// A Boyer-Moore majority finder algorithm implementation.
/// </summary>
/// <typeparam name="T">Type of element stored inside array.</typeparam>
publicstaticclassBoyerMoore<T>whereT:IComparable
{
publicstaticT?FindMajority(IEnumerable<T>input)
{
varcandidate=FindMajorityCandidate(input,input.Count());

if(VerifyMajority(input,input.Count(),candidate))
{
returncandidate;
}

returndefault(T?);
}

// Find majority candidate
privatestaticTFindMajorityCandidate(IEnumerable<T>input,intlength)
{
intcount=1;
Tcandidate=input.First();

foreach(varelementininput.Skip(1))
{
if(candidate.Equals(element))
{
count++;
}
else
{
count--;
}

if(count==0)
{
candidate=element;
count=1;
}
}

returncandidate;
}

// Verify that candidate is indeed the majority
privatestaticboolVerifyMajority(IEnumerable<T>input,intsize,Tcandidate)
{
returninput.Count(x =>x.Equals(candidate))>size/2;
}
}