CODEWITHSUNDEEP
c#.netperformancebinary-search
user3535426
user3535426

Reputation: 41

BinarySearch is so slow

how could it be that when i use the .net BinarySearch on SortedList, it takes far longer then when i use my own self made binary search method on that same list?

using the .net binarysearch:

int ipos = MyList.Keys.ToList().BinarySearch(unSearchFor);

if (ipos >= 0)
{
    // exact target found at position "ipos"
    return MyList[unSearchFor];
}
else
{
    // Exact key not found: 
    // BinarySearch returns negative when the exact target is not found,
    // which is the bitwise complement of the next index in the list larger than the target.
    ipos = ~ipos;
    try
    {
        return MyList.Values[ipos - 1];
    }
    catch
    {
        return null;
    }
}

My binary search method:

int nStart = 0;
int nEnd = MyList.Count - 1;
int mid = 0;

while (nStart <= nEnd)
{
    mid = nStart + (nEnd - nStart) / 2;
    uint unCurrKey = MyList.Values[mid].Key;

    if (unSearchFor == unCurrKey)
        return MyList.Values[mid];

    if (unSearchFor < unCurrKey)
    {
        nEnd = mid - 1;
    }
    else
    {
        nStart = mid + 1;
    }
}

Upvotes: 1

Views: 602

Answers (1)

Hamid Shahid
Hamid Shahid

Reputation: 4626

Isn't it because your are doing a .ToList() when calling BinarySearch() in the list below?

MyList.Keys.ToList().BinarySearch(unSearchFor);

Upvotes: 9

Related Questions