title: Determine whether or not there exist two elements in Set S whose sum is exactly x - correct solution?
body: <p>Taken from Introduction to Algorithms</p>
  
  <blockquote>
    <p>Describe a Θ(n lg n)-time algorithm
    that, given a set S of n integers and
    another integer x, determines whether
    or not there exist two elements in S
    whose sum is exactly x.</p>
  </blockquote>
  
  <p>This is my best solution implemented in Java so far:</p>
  
  <pre><code>    public static boolean test(int[] a, int val) {
      mergeSort(a);
  
      for (int i = 0; i &lt; a.length - 1; ++i) {
          int diff = (val &gt;= a[i]) ? val - a[i] : a[i] - val;
  
          if (Arrays.binarySearch(a, i, a.length, diff) &gt;= 0) {
              return true;
          }
      }
  
      return false;
  }
  </code></pre>
  
  <p>Now my 1st question is: Is this a correct solution? From my understanding, mergeSort should perform the sort in O(n lg n), the loop should take O(n lg n) (n for the iteration multiplied by O(lg n) for the binary search, resulting in O(2n lg n), so it should be correct.</p>
  
  <p>My 2nd question is: Are there any better solutions? Is sorting the array essential?</p>