Binary Search

From programming_contest
Revision as of 02:55, 16 February 2015 by imported>Kmk21
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

discrete

int mask=1,ans=0;
while(mask<max)mask<<=1;
while(mask>0) {
    if(ans+mask<max && function(ans+mask)>=0)ans|=mask;
    mask>>=1;
}

continuous

double mask=1,ans=0;
while(mask<max)mask*=2;
while(mask>epsilon) {
    if(ans+mask<max && function(ans+mask)>=0)ans+=mask;
    mask/=2;
}