return the match index / the next index if no match
int findDownstreamStart( int key)
{
int imax = vectNegStart.size();
int imin = 0;
int imid = (imin + imax) / 2;
if( key <= vectNegStart.get(0))
return 0;
if( key >= vectNegStart.get(imax-1 ))
return imax-1;
// continue searching while [imin,imax] is not empty
while (imax >= imin)
{
/* calculate the midpoint for roughly equal partition */
imid = (imin + imax) / 2;
// determine which subarray to search
if ( vectNegStart.get(imid) < key)
// change min index to search upper subarray
imin = imid + 1;
else if ( vectNegStart.get(imid) > key )
// change max index to search lower subarray
imax = imid - 1;
else
// key found at index imid
return imid;
}
return imid;
}
Comments
Post a Comment