Round integer to nearest high number in array

Question

I have an array of ints like this: [32,128,1024,2048,4096]

Given a specific value, I need to get the closest value in the array that is equal to, or higher than, the value.

I have the following code

  private int GetNextValidSize(int size, int[] validSizes)
  {

      int returnValue = size;

      for (int i = 0; i < validSizes.Length; i++)
      {
          if (validSizes[i] >= size)
          {
              returnValue = validSizes[i];
              break;
          }
      }

      return returnValue;
  }

It works, but is there any better/faster way to do it? The array will never contain more than 5-10 elements.

Clarification: I actually want to return the original value/size if it is bigger than any of the valid sizes. The validSizes array can be considered to always be sorted, and it will always contain at least one value.

Answer 1

It doesn't work. Here are 3 test cases where it fails. In fact, the function interface doesn't have any return result for failure.

I wrote a corrected version, GetNextValidSize2. Since there is no way to return a failure message, I throw an exception for those cases. Here are the results of the run:

test1 : GetNextValidSize failed test1 : GetNextValidSize2 passed test2 : GetNextValidSize Object reference not set to an instance of an object. test2 : GetNextValidSize2 validSizes is nothing test3 : GetNextValidSize passed test3 : GetNextValidSize2 No items in validSizes

By the way, LINQ may be simpler or easier, but it can hardly be more efficient. It can probably be equally efficient if the query optimizer/CLR optimizer work well.

Here's the code - it's in VB since that's what I'm using at the moment, don't want to switch mental gears:

Module Module1

''' <summary>
''' Error - does not work if validSizes is Nothing, or has 0 elements, or if
''' the list contains a validSize that is not the closest one before a closer one,
''' or there are no valid sizes.
''' </summary>
Public Function GetNextValidSize(ByVal size As Integer, ByVal validSizes As List(Of Integer)) As Integer
    Dim returnValue As Integer = size

    For i As Integer = 0 To validSizes.Count - 1 Step 1
        If validSizes.Item(i) >= size Then
            returnValue = validSizes.Item(i)
            Exit For
        End If
    Next
    Return returnValue
End Function

''' <summary>
''' Returns the closest item in validSizes that is >= size. Throws an exception if one cannot 
''' be found.
''' </summary>
 Public Function GetNextValidSize2(ByVal size As Integer, ByVal validSizes As List(Of Integer)) As Integer
    Dim closestValue As Integer = Integer.MaxValue
    Dim found As Boolean = False

    If validSizes Is Nothing Then
        Throw New Exception("validSizes is nothing")
    End If

    If validSizes.Count = 0 Then
        Throw New Exception("No items in validSizes")
    End If

    For Each x In validSizes
        If x >= size Then
            found = True
            If x < closestValue Then
                closestValue = x
            End If
        End If
    Next
    If Not found Then
        Throw New Exception("No items found")
    End If
    Return closestValue
End Function

''' <summary>
''' Output the result of a test.
''' </summary>
 Public Sub outputResult(ByVal testName As String, ByVal result As Boolean, ByVal funcName As String)
    Dim passFail As String
    If result Then
        passFail = " passed"
    Else
        passFail = " failed"
    End If
    Console.WriteLine(testName & " : " & funcName & passFail)
End Sub

''' <summary>
''' Output the result of a test where an exception occurred.
''' </summary>
 Public Sub outputResult(ByVal testName As String, ByVal ex As Exception, ByVal funcName As String)

    Console.WriteLine(testName & " : " & funcName & " " & ex.Message())
End Sub

''' <summary>
''' Test with a list of 3 integers
''' </summary>
 Public Sub test1()
    Dim aList As New List(Of Integer)
    aList.Add(5)
    aList.Add(4)
    aList.Add(3)
    Dim result = GetNextValidSize(3, aList)
    outputResult("test1", 3 = GetNextValidSize(3, aList), "GetNextValidSize")
    outputResult("test1", 3 = GetNextValidSize2(3, aList), "GetNextValidSize2")
End Sub

''' <summary>
''' Test with a null reference
''' </summary>
Public Sub test2()
    Dim aList = Nothing
    Try
        outputResult("test2", GetNextValidSize(3, aList), "GetNextValidSize")
    Catch ex As Exception
        outputResult("test2", ex, "GetNextValidSize")
    End Try
    Try
        outputResult("test2", GetNextValidSize2(3, aList), "GetNextValidSize2")
    Catch ex As Exception
        outputResult("test2", ex, "GetNextValidSize2")
    End Try
End Sub

''' <summary>
''' Test with an empty array.
''' </summary>
Public Sub test3()
    Dim aList As New List(Of Integer)
    Try
        outputResult("test3", GetNextValidSize(3, aList), "GetNextValidSize")
    Catch ex As Exception
        outputResult("test3", ex, "GetNextValidSize")
    End Try
    Try
        outputResult("test3", GetNextValidSize2(3, aList), "GetNextValidSize2")
    Catch ex As Exception
        outputResult("test3", ex, "GetNextValidSize2")
    End Try
End Sub

''' <summary>
''' Run all tests.
''' </summary>
Public Sub testAll()
    test1()
    test2()
    test3()
End Sub

Sub Main()
    testAll()
    Console.ReadLine()
End Sub

End Module

Answer 2

You could use LINQ to simplify the query - it will probably be as fast as anything you could write if your list is sorted.

int someInitialValue;
int defaultIfNotFound = ... // set to some value, even initialValue
// attempt to find first value less than or equal
int bestMatch = myListOfValues.Concat( new []{defaultIfNotFound} )
                              .FirstOrDefault( x => x >= someInitialValue );

If the array is not ordered, or if you need better performance:

myListOfValues.OrderBy( x => x ).Concat( new []{defaultIfNotFound} )
                                .FirstOrDefault( x => x >= someInitialValue );

You mention that you list is relatively small (5-10 items) - so linear search is probably fast enough. However, on a larger list (dozens or hundreds of items), you may want to consider using a binary search to find the value:

// index is positive if an exact match is found
// if no exact match is found, the index returned will be two's complement and
// reference the next number immediately larger than the search target
int index = myListOfValues.BinarySearch( someInitialValue );
if( index < 0 && ~index > myListOfValues.Length )
   bestMatch = someInitialValue;
else
   bestMatch = index < 0 ? myListOfValues[~index] : myListOfValues[index];

Answer 3

With only 5-10 elements, definitely go with the simplest solution. Getting a binary chop working would help with a larger array, but it's got at least the potential for off-by-one errors.

Rather than breaking, however, I would return directly from the loop to make it even simpler, and use foreach as well:

  private int GetNextValidSize(int size, int[] validSizes)
  {    
      int returnValue = size;

      foreach (int validSize in validSizes)
      {
          if (validSize >= size)
          {
              return validSizes;
          }
      }

      // Nothing valid    
      return size;
  }

You can make this even simpler with LINQ:

// Make sure we return "size" if none of the valid sizes are greater
return validSizes.Concat(new[] { size })
                 .First(validSize => validSize >= size);

It would be even simpler without the Concat step... or if there were a Concat method that just took a single element. That's easy to write, admittedly:

public static IEnumerable<T> Concat(this IEnumerable<T> source,
                                    T tail)
{
    foreach (T element in source)
    {
        yield return element;
    }
    yield return tail;
}

then it's just:

return validSizes.Concat(size).First(validSize => validSize >= size);

Alternatively (and I realise I'm presenting way more options than are really needed here!) an overload for FirstOrDefault which took the default value to return:

public static T FirstOrDefault(this IEnumerable<T> source,
                               Func<T, bool> predicate,
                               T defaultValue)
{
    foreach (T element in source)
    {
        if (predicate(element))
        {
            return element;
        }
    }
    return defaultValue;
}

Call it like this:

return validSizes.FirstOrDefault(validSize => validSize >= size, size);

Both of these are overkill for a single use, but if you're already building up a library of extra LINQ operators, it could be useful.

Answer 4

I think you will just get the first greater number, not necessarily the closest greater number.

If your array isn't sorted, you'll need to double-pass it to find the right number. First you'll find the greatest, and second the smaller value that is still greater than the original value.

Answer 5

If your array is ordered, you can fast this up by using a binary search algorithm.

See there: http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 6

int[] validSizes = new int[] { 32, 128, 1024, 2048, 4096 };

int sizeICareAbout = 4096;

Console.Write(validSizes.Max(i => i < sizeICareAbout ? i : Int32.MinValue));

This will return Int32.MinValue if you put in the smallest value. God, I love LINQ.

Answer 7

Given that you have only 5-10 elements I would consider this to be ok.