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

Question

In CodinGame learning platform, one of the questions used as an example in a C# tutorial is this one:

The aim of this exercise is to check the presence of a number in an array.

Specifications: The items are integers arranged in ascending order. The array can contain up to 1 million items. The array is never null. Implement the method boolean Answer.Exists(int[] ints, int k) so that it returns true if k belongs to ints, otherwise the method should return false.

Important note: Try to save CPU cycles if possible.

Example:

int[] ints = {-9, 14, 37, 102};

Answer.Exists(ints, 102) returns true.
Answer.Exists(ints, 36) returns false.

My proposal was to do that:

using System;
using System.IO;

public class Answer
{
    public static bool Exists(int[] ints, int k)
    {
        foreach (var i in ints)
        {
            if (i == k)
            {
                return true;
            }

            if (i > k)
            {
                return false;
            }
        }

        return false;
    }
}

The result of the test was:

• ✔ The solution works with a 'small' array (200 pts) - Problem solving
• ✔ The solution works with an empty array (50 pts) - Reliability
• ✘ The solution works in a reasonable time with one million items (700 pts) - Problem solving

I don't get the last point. It appears that the code may be more optimal than the one I suggested.

How to optimize this piece of code? Is a binary search an actual solution (given that the values in the array are already ordered), or there is something simpler that I missed?

Answer 1

Yes, I think that binary search O(log(N)) complexity v. O(N) complexity is the solution:

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

since Array.BinarySearch return non-negative value if the item (k) has been found:

https://msdn.microsoft.com/en-us/library/2cy9f6wb(v=vs.110).aspx

Return Value Type: System.Int32 The index of the specified value in the specified array, if value is found; otherwise, a negative number.

Answer 2

Here is a fast method for an ordered array

public static class Answer
{
    public static bool Exists( int[] ints, int k )
    {
        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 );
    }
}

Takes around 50 ticks on my cpu (with 90.000.000 items in the array)

Sample on dotnetfiddle

Answer 3

class Answer
{
    public static bool Exists(int[] ints, int k)
    {
        int index = Array.BinarySearch(ints, k);
        if (index > -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    static void Main(string[] args)
    {
        int[] ints = { -9, 14, 37, 102 };
        Console.WriteLine(Answer.Exists(ints, 14)); // true
        Console.WriteLine(Answer.Exists(ints, 4)); // false
    }

}