title: How to save CPU cycles when searching for a value in a sorted list?
body: <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>