How to speed up the process of looping a million values array?

Question

So I was taking an online test where i had to implement a piece of code to simply check if the value was in the array. I wrote the following code:

    using System;
    using System.IO;
    using System.Linq;

    public class Check
    {
        public static bool ExistsInArray(int[] ints, int val)
        {
            if (ints.Contains(val)) return true;
            else return false;
        }
    }

Now i didn't see any problems here because the code works fine but somehow i still failed the test because this is "not fast enough" once the array contains a million values.

The only code i wrote myself is:

    if (ints.Contains(val)) return true;
    else return false;

The other code i was given to work with.

Is there a way to speed up this process?

Thanks in advance.

EDIT: I came across a page where someone apparently took the same test as i took and it seems to come down to saving CPU cycles.

Reference: How to save CPU cycles when searching for a value in a sorted list?

Now his solution within the method is:

    var lower = 0;
    var upper = ints.Length - 1;

    if ( k < ints[lower] || k > ints[upper] ) return false;
    if ( k == ints[lower] ) return true;
    if ( k == ints[upper] ) return true;

    do
    {
        var middle = lower + ( upper - lower ) / 2;

        if ( ints[middle] == k ) return true;
        if ( lower == upper ) return false;

        if ( k < ints[middle] )
            upper = Math.Max( lower, middle - 1 );
        else
            lower = Math.Min( upper, middle + 1 );
    } while ( true );

Now i see how this code works but it's not clear to me why this is supposed to be faster. Would be nice if someone could elaborate.

Answer 1

If it's sorted array you can use BinarySearch To speed Up the process

public static bool ExistsInArray(int[] ints, int val)
{
    return Array.BinarySearch(ints, val) >= 0;
}