CODEWITHSUNDEEP
c#arrayssearch
Addie
Addie

Reputation: 31

index of closest a number in array, closest to x, that cannot be larger than x

How can I write a function that accepts an array of integers and an integer x and returns the index of the integer in the array that is closest to x argument without being larger than x. If all are above x, the function will return negative one. Assuming two or more numbers cannot be the same in array.

Upvotes: 1

Views: 44

Answers (2)

fubo
fubo

Reputation: 45947

assuming that are numbers are unique you could use

public static int GetClosestIndex(int[] arr, int value)
{
    var result = arr.Where(x => x < value).OrderByDescending(x => x);
    return result.Any() ? Array.IndexOf(arr, result.FirstOrDefault()) : -1;
}

Update: (for Zastai)

here is a better performing approach

public static int GetClosestIndex(int[] arr, int value)
{
    int result = -1;
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] < value)
        {
            if (result == -1 || arr[i] > arr[result])
            {
                result = i;
            }
        }
    }
    return result;
}

Upvotes: 2

Zastai
Zastai

Reputation: 1265

I'd go with

public static class StackOverflow {

public static int IndexOfValueClosestTo<T>(this IList<T> list, T x) where T : IComparable<T> {
  var closestValue = default(T);
  var closestIndex = -1;
  var idx = -1;
  foreach (var v in list) {
    ++idx;
    if (v.CompareTo(x) < 0 && (closestIndex == -1 || closestValue.CompareTo(v) < 0)) {
      closestIndex = idx;
      closestValue = v;
    }
  }
  return closestIndex;
}

}

It is still very readable, works on arrays, lists, ... and handles integers, doubles, ... It's also an extension method, so you can use both StackOverflow.IndexOfValueClosestTo(mylist, myvalue) and mylist.IndexOfValueClosestTo(myvalue).

Some basic benchmarks in LINQPad with an array of a million elements also show this to be 30 times faster than the LINQ-based answer (with 100 iterations this takes ~1.05s where the LINQ version takes ~37s).

For the absolute best performance, however, use a version specialized to int arrays:

public static int IndexOfValueClosestTo(this int[] list, int x) {
  var closestValue = 0;
  var closestIndex = -1;
  var idx = -1;
  foreach (var v in list) {
    ++idx;
    if (v < x && (closestIndex == -1 || closestValue < v)) {
      closestIndex = idx;
      closestValue = v;
    }
  }
  return closestIndex;
}

That runs the 100 iterations in ~0.33s, so it's about 3 times as fast as the generic version above. Note that you can define both as overloads, so you still have a working implementation for, say, a list of doubles.

Upvotes: 2

Related Questions