Find the largest value smaller than x in a sorted array

Question

Suppose I have a sorted array of integers int[], and I want to search the closest smaller value to some input number.

for example if the array contains (1) , (23), (57) , (59), (120) and the input is 109, the output should be 59.

I am just trying to see suggestions and compare to the approaches I already have.

Answer 1

Use Array.BinarySearch. If the input is in the list, it will return the index, and if not then it will return the complement of the index of the first larger value. You just invert the result and subtract one to get the index of the closest smaller value.

int[] arr = { 1, 23, 57, 59, 120 };
int index = Array.BinarySearch(arr, 109);
if (index < 0)
{
    index = ~index - 1;
}
if (index >= 0)
{
    var result = arr[index];
}

Note that if you have an input smaller than the smallest element, you don't have a well-defined answer.

Answer 2

using Linq:

int[] arr = new[] { 1, 23, 57, 59, 120 };
int target = 109;
int max = arr.Where(n => n < target).Max();

Maybe not the fastest but probably the easiest to implement. Also doesn't rely on the array being sorted, as binary search does.

Note that the call to Max will throw an exception if the Where filter results in no elements, so you might want to check that if it's a possibility.

Answer 3

I'd go for a linq solution (updated: to add a little more code to stop from being similar to fear's similar solution):

int[] arr1 = { 1, 23, 57, 59, 120 };
int maxResult;
string errorMsg;
try
{
    maxResult = arr1.Where(x => x <= 109).Max();
}
catch(Exception e)
{
    errorMsg = e.Message;
    // do some error stuff here :)
    return null;
}
// party on your maxResult...

Answer 4

int getIndex( long[] list, long value )
{
    int top = 0;
    int bot = list.length-1;
    int mid=0;
    while ( top <= bot )
    {
        mid = (top+bot)/2; // NB integer arithmetic
        if ( value < list[mid] )
        {
            if ( mid == 0 )
                // value < than first item
                return -1;  
            else
                bot = mid-1;
        }
        else    // value >= list[mid]
        {
            if ( mid == list.length-1 )
                // value is >= last item
                break;
            else if ( value >= list[mid+1] )
                top = mid+1;
            else // list[mid] must be biggest <= value
                break;
        }
    }
    return mid;
}

Answer 5

just to extrapolate on the other LINQ solutions this extension method will return -1 if no objects fits the filter and expects that the list is all positive integers

public static int SearchForLimit(this IEnuemerable<int> sequence, Predicate<int> filter)
{
   return (from i in sequence
           let n = filter(i) ? i : -1
           select n).Max()
}

usage would look like this:

int[] arr1 = { 1, 23, 57, 59, 120 };
int limitedBy109 = arr1.SearchForLimit(i => i < 109);