BinarySearch is so slow

Question

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;
    }
}

The first does binary search on collection of keys, the second one doesn't seem to touch keys of the collection. Are you sure these two algorithms are doing the same thing? — Tomas Pastircak, Apr 22 '14 at 15:50
Possibly the exceptions? Those are expensive to throw and catch, and the different algorithm in the second doesn't appear to throw/catch exceptions in order to `return null`. We're really just guessing without your test data set and info on your benchmarking approach. — Tim S., Apr 22 '14 at 15:51
Can't agree exceptions are expensive: if throw-catch in a massive loop then yes, otherwise - no. And not a performance bottleneck for sure. — abatishchev, Apr 22 '14 at 15:52
The reason to avoid the try-catch is not for performance. It's because you're using an exception where a simple `if` would do. **Do not use exceptions as an unexceptional-scenario control flow mechanism**. This is a very bad programming practice. — Eric Lippert, Apr 22 '14 at 16:26
@abatishchev: Having a try-catch anywhere in a method can cause the C# compiler or jitter to sometimes generate less efficient code than it otherwise would have. (Not shown in this code, but a clear example of why the compiler / jitter must generate less efficient code: copy elision optimizations on value type construction.) — Eric Lippert, Apr 22 '14 at 20:56

score 9 · Answer 1 · answered Apr 22 '14 at 15:48

9

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

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

answered Apr 22 '14 at 15:48

Hamid Shahid

4,486
3
32
41

3

Not sure why you got the -1. The first algorithm is O(n) where a proper binary search is O(log n). You have certainly located an algorithm error in the example that would substantially impact performance. – Sam Harwell Apr 22 '14 at 15:54
i have to ToList in order to call BinarySearch, is this method time expensive? i thought it was just changing the type.. – user3535426 Apr 25 '14 at 10:31
Yes it has an O(n) performance impact. http://stackoverflow.com/questions/15516462/is-there-a-performance-impact-when-calling-tolist – Hamid Shahid Apr 29 '14 at 10:15
@user3535426 couldy you please mark this as an answer – Hamid Shahid Nov 03 '17 at 18:28

BinarySearch is so slow

1 Answers1