C# Binary Search Variation

Question

The list is sorted.

I have a List and I d like to do binary search on it. T has members like StartIndex, EndIndex etc.

I can do binary search on the list with StartIndex, ie: I have implemented IComparable for this.

I need to twist this a little as the following: I want to find a StartIndex that might be OffBy a small value.

For example : T.StartIndex= 100

if the input is 101 and OffBy 1 then BinarySearch Should return this object.

How can I do this?

BTW, i m asking how to this with default binarysearch method that List has. That s what i m interested, not interested in a custom binary search implementation.

Answer 1

If you use List<T>.BinarySearch then it will find the exact position of one exists, or return the bitwise complement of the index at which you would need to insert the item.

So if it returns a negative number, just check the next and previous items (being careful of the ends of course) to see whether either of those is within your desired tolerance.

For example:

int index = list.BinarySearch(item);
if (index < 0)
{
    int candidate = ~index;
    if (candidate > 0 && 
        Math.Abs(list[candidate - 1].StartIndex - item.StartIndex) <= tolerance)
    {
        index = candidate - 1;
    }
    else if (candidate < list.Count - 1 && 
         Math.Abs(list[candidate + 1].StartIndex - item.StartIndex) <= tolerance)
    {
         index = candidate + 1;
    }
    else
    {
         // Do whatever you need to in the failure case
    }
}
// By now, index is correct