Binary Search

// ( c ) 2005 James Killian

//returns -1 if exact match is not found
//If an exact match isn't found like in the case of using a discontinuity table... you can find the closest index
//represented to it by providing a pointer to the Low and High Result parameters... these only are valid if there
//is no match, because that means they zero'd in on the key as close as possible... if the key is out of range of
//the entire list... the low or high result will return negative one...
template class < KeyType,class ListType >
unsigned tBinarySearch (
    ListType ListToUse,
    KeyType Key,
    unsigned NoItems,
    //return 0 when equal, return Neg if PtrToFindScanElement
    int (*compare)(KeyType,ListType,unsigned ScanPos),
    //These are optional if you wish to find the closest index range found (Only if there is no exact match!)
    unsigned *LowResult=NULL,
    unsigned *HighResult=NULL
    )
{

    unsigned lo=0;
    unsigned hi=(NoItems-1);
    unsigned mid;
    unsigned result=-1;
    int TestCompare;

    if (NoItems)
    {
        do
        {
            mid=((hi+lo)>>1);
            if (!(TestCompare = (*compare)(Key,ListToUse,mid)))
            {
                result=mid;
                break;
            }
            else
            {
                if (TestCompare<0)
                    hi=mid;
                else
                    lo=mid;
            }
        } while (hi-lo>1);

        //In this design the mid computation always trunicates the decimal value.. so computing mid will always be one
        //under hi... this necessitates the break to occur when hi-lo are 1 unit apart; consequently this means I'll
        //need to test the lo and hi explicitly one last time to finish the search (If a match has not been found already)


        if (result==-1)
        {
            do
            {

                if (!(TestCompare = (*compare)(Key,ListToUse,lo)))
                {
                    result=lo;
                    break;
                }
                if (TestCompare<0) //This means the key is less than the entire list
                {
                    hi=lo;
                    lo=-1;
                    break;
                }

                if (!(TestCompare = (*compare)(Key,ListToUse,hi)))
                {
                    result=hi;
                    break;
                }
                if (TestCompare>0) //This means the key is greater than the entire list
                {
                    lo=hi;
                    hi=-1;
                }
            } while (false);
        }
    }
    else
        lo=-1;

    if (LowResult)
        *LowResult=lo;

    if (HighResult)
        *HighResult=hi;

    return result;
}