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
    }

}

Answer 4

Apparently, the task intends we use the default binary search method instead of implementing one. I was also somewhat surprised it is what it evaluates for in 3rd test. "The solution uses the standard library to perform the binary search (iterating on ints)"

Which kinda is confusing, they could have mentioned this in the code instead of giving some 15 - 20 minutes to solve. which is another reason for this confusion.

This is what I wrote for that question -> dividing array to half and search the half -> a more rudimentary way of implementing it...

int half = size/2;
if( k < ints[half])
{
    for(int i=0; i < half; i++)
    {
        if( k == ints[i])
        {
             return true;
        }
    }
}
else
{
    for(int i=half; i < size; i++)
    {
        if( k == ints[i])
        {
            return true;
        }                
    }
 }

Answer 5

 public static bool Exists(int[] ints, int k)
        {
            var d = 0;
            var f = ints.Length - 1;
            if (d > f) return false;
            if (k > ints[f] || k < ints[d]) return false;
            if (k == ints[f] || k == ints[d]) return true;
            return (BinarySearch(ints, k, d, f) > 0);
        }

 public static int BinarySearch(int[] V, int Key, int begin, int end)
        {
            if (begin > end)
                return -1;
            var MidellIndex = (begin + end) / 2;

            if (Key == V[MidellIndex])
                return MidellIndex;
            else
            {
                if (Key > V[MidellIndex])
                {
                    begin = MidellIndex + 1;
                    return BinarySearch(V, Key, begin, end);
                }
                else
                {
                    end = MidellIndex - 1;
                    return BinarySearch(V, Key, begin, end);
                }
            }

        }

Answer 6

I saw the all solutions, by the way I create and test the following recursive approach and get the complete points:

public static bool Exists(int[] ints, int k)
    {


        if (ints.Length > 0 && ints[0] <= k && k <= ints[ints.Length - 1])
        {
            if (ints[0] == k || ints[ints.Length - 1] == k) return true;
            return SearchRecursive(ints, k, 0, ints.Length - 1) != -1;
        }
        return false;
    }

    private static int SearchRecursive(int[] array, int value, int first, int last)
    {
        int middle = (first + last) / 2;

        if (array[middle] == value)
        {
            return middle;
        }
        else if (first >= last)
        {
            return -1;
        }
        else if (value < array[middle])
        {
            return SearchRecursive(array, value, first, middle - 1);
        }
        else
        {
            return SearchRecursive(array, value, middle + 1, last);
        }
    }

Answer 7

Yes, BinarySearch would be faster than most algorithms you can write manually. However, if the intent of the exercise is to learn how to write an algorithm, you are on the right track. Your algorithm, though, makes an unnecessary check with if (i > k) ... why do you need this?

Below is my general algorithm for simple requirements like this. The while loop like this is slightly more performant than a for-loop and out performs a foreach easily.

public class Answer
{
    public static bool Exists(int[] ints, int k)
    {
        var i = 0;
        var hasValue = false;

        while(i < ints.Length && !hasValue)
        {
            hasValue = ints[i] == k;
            ++i;
        }

        return hasValue;
    }
}

Answer 8

If you are trying to squeeze every ounce of speed out of it... consider that your array has 1..100 and you want to search for 78. Your algorithm needs to search and compare 78 items before you find the right one. How about instead you search the first item and its not there, so you jump to array size / 2 and find 50? Now you skipped 50 iterations. You know that 78 MUST be in the top half of the array, so you can again split it in half and jump to 75, etc. By continuously splitting the array in half, you do much fewer iterations then your brute force approach.