title: O(n log(n)) algorithm that checks if sum of 2 numbers in a int[] = given number
body: <p>I am supposed to create a <code>O(n log(n))</code> algorithm that checks if sum of 2 numbers in a int[] == given number. </p>
  
  <p>eg. Given [1,4,7,2,3,4] there will be a sum 8 (1+7) but not 20</p>
  
  <p>The given answer suggested Binary Sort or Merge Sort, but they just gave the merge sort algorithm without the logic processing this particular requirement. Then another answer was: </p>
  
  <blockquote>
    <p>Suppose x is the sum we want to check, z is the set of elements in
    this array: The following algorithm solves the problem:</p>
    
    <ol>
    <li>Sort the elements in S.</li>
    <li>Form the set S’ = {z : z = x − y for some y ∈ S}.</li>
    <li>Sort the elements in S'.</li>
    <li>If any value in S appears more than once, remove all but one instance. Do the same for S’.</li>
    <li>Merge the two sorted sets S and S’.</li>
    <li>There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.</li>
    </ol>
    
    <p>To justify the claim in step 4, first observe that if any value
    appears twice in the merged output, it must appear in consecutive
    positions. Thus, we can restate the condition in step 5 as there exist
    two elements in S whose sum is exactly x if and only if the same value
    appears twice in the merged output. Suppose that some value w appears
    twice. Then w appeared once in S and once in S’. Because w appeared in
    S’, there exists some y ∈ S such that w = x − y, or x = w + y. Since w
    ∈ S, the elements w and y are in S and sum to x.</p>
    
    <p>Conversely, suppose that there are values w, y ∈ S such that w + y =
    x. Then, since x − y = w, the value w appears in S’. Thus, w is in
    both S and S’, and so it will appear twice in the merged output.</p>
    
    <p>Steps 1 and 3 require O(n log n) steps. Steps 2, 4, 5, and 6 require
    O(n) steps. Thus the overall running time is O(n log n).</p>
  </blockquote>
  
  <p>But I don't really what they meant. In step 2, what are x and y?</p>
  
  <p>But I created by own below, I wonder if its <code>O(n log(n))</code>?</p>
  
  <pre><code>class FindSum {
  
    public static void main(String[] args) {
      int[] arr = {6,1,2,3,7,12,10,10};
      int targetSum = 20;
  
      Arrays.sort(arr);
      System.out.println(Arrays.toString(arr));
      int end = arr.length - 1;
      if (FindSum.binarySearchSum(arr, targetSum, 0, end, 0, end)) {
        System.out.println("Found!");
      } else {
        System.out.println("Not Found :(");
      }
    } 
  
    public static boolean binarySearchSum(int[] arr, int targetSum,
                                          int from1, int end1,
                                          int from2, int end2) {
      // idea is to use 2 "pointers" (simulating 2 arrays) to (binary) search 
      // for target sum
      int curr1 = from1 + (end1-from1)/2;
      int curr2 = from2 + (end2-from2)/2;
      System.out.print(String.format("Looking between %d to %d, %d to %d: %d, %d", from1, end1, from2, end2, curr1, curr2));
      int currSum = arr[curr1] + arr[curr2];
      System.out.println(". Sum = " + currSum);
  
      if (currSum == targetSum) { 
        // base case
        return true;
      } else if (currSum &gt; targetSum) { 
        // currSum more than targetSum
        if (from2 != end2) { 
          // search in lower half of 2nd "array"
          return FindSum.binarySearchSum(arr, targetSum, from1, end1, from2, curr2 - 1);
        } else if (from1 != end2) { 
          // search in lower half of 1st "array" (resetting the start2, end2 args)
          return FindSum.binarySearchSum(arr, targetSum, from1, curr1 - 1, 0, arr.length - 1);
        } else {
          // can't find
          return false;
        }
      } else {
        // currSum &lt; targetSum
        if (from2 != end2) { 
          // search in upper half of 2nd "array"
          return FindSum.binarySearchSum(arr, targetSum, from1, end1, curr2 + 1, end2);
        } else if (from1 != end2) { 
          // search in upper half of 1st "array" (resetting the start2, end2 args)
          return FindSum.binarySearchSum(arr, targetSum, curr1 + 1, end1, 0, arr.length - 1);
        } else {
          // can't find
          return false;
        }
      }
    }
  
  }
  </code></pre>