Skip to main content

java binary search





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