title: How do I optimise the code to return the number closest to a given integer, not present in the given list?
body: <p>I solved <a href="https://atcoder.jp/contests/abc170/tasks/abc170_c" rel="nofollow noreferrer">this</a> problem statement (Yeah Yeah, I know, I am putting the problem statement below).</p>
  
  <hr>
  
  <blockquote>
    <p>Given are an integer X and an integer sequence of length N: p1, …, pN.
    Among the integers not contained in the sequence p1, …, pN (not necessarily positive), 
    find the integer nearest to X, i.e. the integer whose absolute difference with X is the minimum. 
    If there are multiple such integers, report the smallest such integer</p>
  </blockquote>
  
  <hr>
  
  <p>This is the code I used:</p>
  
  <pre><code>#include &lt;algorithm&gt;
  #include &lt;cstdlib&gt;
  #include &lt;iostream&gt;
  #include &lt;numeric&gt;
  #include &lt;vector&gt;
  
  int main() {
      int x = 0;
      int n = 0;
      std::cin &gt;&gt; x &gt;&gt; n;
      std::vector&lt;decltype(x)&gt; vect(n);
      bool vect_contains_x = false;
      for (auto&amp; elem : vect) {
          std::cin &gt;&gt; elem;
          if (elem == x) {
              vect_contains_x = true;
          }
      }
      int num = 0;
      if (!vect_contains_x) {
          num = x;
      }
      else {
          std::sort(vect.begin(), vect.end());
          while (1) {
              static int i = 1;
              if (std::find(vect.begin(), vect.end(), x - i) == vect.end()) {
                  num = x - i;
                  break;
              }
              else if (std::find(vect.begin(), vect.end(), x + i) == vect.end()) {
                  num = x + i;
                  break;
              }
              else {
                  i += 1;
              }
          }
      }
      std::cout &lt;&lt; num &lt;&lt; "\n";
      return 0;
  }
  </code></pre>
  
  <p>This code renders the result in <code>13-18ms</code>. </p>
  
  <hr>
  
  <p>I was able to get it down to <code>8-10ms</code> by using the following optimised code:</p>
  
  <pre><code>#include &lt;algorithm&gt;
  #include &lt;cstdlib&gt;
  #include &lt;iostream&gt;
  #include &lt;numeric&gt;
  #include &lt;vector&gt;
  
  int main() {
      int x = 0;
      int n = 0;
      std::cin &gt;&gt; x &gt;&gt; n;
      std::vector&lt;decltype(x)&gt; vect(n);
      bool vect_contains_x = false;
      for (auto&amp; elem : vect) {
          std::cin &gt;&gt; elem;
          if (elem == x) {
              vect_contains_x = true;
          }
      }
      int num = 0;
      if (!vect_contains_x) {
          num = x;
      }
      else {
          std::sort(vect.begin(), vect.end());
          auto isPresent = [=](auto num) {
              for (const auto&amp; elem : vect) {
                  if (num == elem) {
                      return true;
                  }
              }
              return false;
          };
          while (1) {
              static int i = 1;
              if (!isPresent(x - i)) {
                  num = x - i;
                  break;
              }
              else if (!isPresent(x + i)) {
                  num = x + i;
                  break;
              }
              else {
                  i += 1;
              }
          }
      }
      std::cout &lt;&lt; num &lt;&lt; "\n";
      return 0;
  }
  </code></pre>
  
  <hr>
  
  <p>However, the problem with both the codes (as they both use the same approach) is that,
  If there is a large continuous stream of integers in the given list, something like:</p>
  
  <blockquote>
    <p>1,2,3,4,5,6,7,8,9,10,...,1501</p>
  </blockquote>
  
  <p>and the X given is </p>
  
  <blockquote>
    <p>751</p>
  </blockquote>
  
  <hr>
  
  <p>The code will need 750 iterations of the <code>for loop</code>, which is a lot. Can we use a better algorithm to find the closest integer?</p>
  
  <hr>
  
  <p><strong>EDIT</strong>:</p>
  
  <p>Got it down to <code>6ms</code> by using <code>binary_search</code> (Thanks @Sebastian), but still, the algorithm remains the same...</p>