How do I check if int[] contains only certain numbers?

Question

I need to check that an int[] contains only certain values (in this case 0s & 1s) and throw an exception if it doesn't.

Is there a more efficient way to do it than either of the following solutions?

Simple (but O(n)):

for(int n = 0; n < myArray.Length; n++)
    if(!(myArray[n] == 0 || myArray[n] == 1))
        throw new Exception("Array contains invalid values");

Using Where():

if(myArray.Where(n => !(n==1 || n==0)).ToArray().Length > 0)
    throw new Exception("Array contains invalid values");

Stephanestephani

Do you want to stop processing when you encounter an invalid value, or do you want to validate the entire collection ? – Dilworth

Under the constraints, your for loop is the best you can get. Looks like you think LINQ can do "magic" because you didn't say O(N) for the "using Where()" – Kidding

Also, I can't help thinking of this – Sorrells

No need to validate the entire array as any single error is a fail. As for Where(), I wasn't sure if it would've made some subtle under-the-hood differences or not. – Stephanestephani

Answer 1

You can't check an array without iterating through it. So O(n) is the best you are going to get. The other solution would be to control loading the array and throw an exception when somebody tries to put a value that isn't 0 or 1 in it. Another solution might be to use a bool[] which only has two possible values anyway, but would require some conversion if you actually need numbers. (Note: if you needed more than two values, it might make sense to look at an enum, especially if those values are supposed to represent something)

Also, Where is not the best solution here because you are forced to check the whole array (no early exit). Use Any instead (but it's still doing basically what your for loop is doing - best case O(1), worse O(n) average O(n)).

if (myArray.Any(a => a != 0 && a != 1))
{
     // ....
}

Sorrells

Thanks for the pointer towards Any() Gonna have to stick with ints, as the rest of the program relies on them. – Stephanestephani

Answer 2

You can try to use Array.TrueForAll:

if (!Array.TrueForAll(myArray, n => n == 0 || n == 1))
     throw new Exception("Array contains invalid values");

Complice

Per MSDN Documentation here: msdn.microsoft.com/en-us/library/kdxe4x4w(v=vs.110).aspx This is still O(n), although it's at least a little cleaner anyways. – Remorseless

Answer 3

Here is research blog post according to your question http://www.tkachenko.com/blog/archives/000682.html

tested on

int[] data = new int[100000000];

if you are really interested in performance you shouldn't use Any() for sure )))))

so as far you need to search for couple values in array the unswer is - for loop search or foreach (in your case of int[] compiled into the CIL as for loop) is the best options for you

foreach loop search:            39 ms
for loop search:                39 ms
Contains() method search:       56 ms
Any() method search:            446 ms
IndexOf() method search:        57 ms

Mcclinton

you shouldn't use Any() for sure, if you don't have a 100 million element array, I wouldn't worry about it unless it is revealed to be an actual bottleneck in your actual code. – Sorrells

@MattBurland you are right, but I wrote "if you are really interested in performance ...", also if you take a look at the Any() compiled into the CIL you'll see how Any() differs from the for loop and test numbers show this difference on practice – Mcclinton