How to save CPU cycles when searching for a value in a sorted list?
<p>In <a href="https://www.codingame.com/" rel="noreferrer">CodinGame</a> learning platform, one of the questions used as an example in a C# tutorial is this one:</p>

<blockquote>
  <p>The aim of this exercise is to check the presence of a number in an
  array.</p>
  
  <p>Specifications: The items are integers arranged in ascending order.
  The array can contain up to 1 million items. The array is never <code>null</code>.
  Implement the method boolean <code>Answer.Exists(int[] ints, int k)</code> so that
  it returns <code>true</code> if <code>k</code> belongs to <code>ints</code>, otherwise the method should
  return <code>false</code>.</p>
  
  <p>Important note: Try to save CPU cycles if possible.</p>
  
  <p>Example:</p>

<pre><code>int[] ints = {-9, 14, 37, 102};
</code></pre>
  
  <p><code>Answer.Exists(ints, 102)</code> returns <code>true</code>.<br>
  <code>Answer.Exists(ints, 36)</code> returns <code>false</code>.</p>
</blockquote>

<p>My proposal was to do that:</p>

<pre><code>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 &gt; k)
            {
                return false;
            }
        }

        return false;
    }
}
</code></pre>

<p>The result of the test was:</p>

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

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

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