.NET 2.0 offers an easy way to find any item of a generic list that is sorted by the item to get using a binary search that has an order of O(ln N). But what if you need to find an item that has not the exact value and you want to find the item that is lower/equal or higher/equal? Fortunately, the BinarySearch method also supports this situation:

BinarySearch returns the item index that matches the item to find, otherwise the return value is less than zero. But this value is a negative value that represents the nearest item that is lower than the item to search minus 2.

The following example uses this feature to find an item that is either equal or less than the index to search for:

First, a comparer class is derived that compares the items. The constructor has a parameter for the index to find instead of specifying a class for the BinarySearch method. As the BinarySearch will be parameter less, the second parameter for the Compare method will always be null and can be ignored:

        /// <summary>
        /// A comparer class to compare the groups list to find a item faster using binary search.
        /// </summary>
        class MyComparer : IComparer<MyClass>:IDisposable
        {
            public MyComparer(int index)
                : base()
            {
                this.index = index;
            }
           private int index;
 
            public int Compare(MyClass x, MyClass y)
            {
                return x.index - index;
            }
         }

The following method LowerOrEqualValue finally performs the search by creating a MyComparer class. If the result value of BinarySearch is positive or null, an item with exact the required index exists, otherwise the index is a negative value of the nearest index that is less than the specified index, so we make it positive with the formula

resultIndex = -2 – resultIndex

Note that, if there is really no item, the return value would be -1 so the formula finally would also be -1.

 
       private int LowerOrEqualValue(int index)
        {
            using (MyComparer comparer = new MyComparer (index))
            {
                int resultIndex = items.BinarySearch(null, comparer);
                if (resultIndex < 0) resultIndex = -2 - resultIndex;
                if (resultIndex >= 0 && resultIndex < resultIndex.Count)
                {
                    return resultIndex;
                }
                return -1;
            }
        }

If you don't need the next lower item but the next higher value, you just need to replace the formula by

resultIndex = -1-resultIndex

But then you must explicitly check the situation of no result when BinarySearch returns -1!