Given an array A[] of n numbers and another number x, the task is to check whether or not there exist two elements in A[] whose sum is exactly x.


Example 1:


Input: arr[] = {0, -1, 2, -3, 1}, x= -2

Output: true

Explanation:  If we calculate the sum of the output,1 + (-3) = -2


Example 2:


Input: arr[] = {1, -2, 1, 0, 5}, x = 0

Output: false


We will be using binary search to find the sum.


Sort the array, then traverse the array elements and perform binary search for (target – a[i]) on the remaining part


Follow the below steps to solve the problem:


  • Sort the array in non-decreasing order.
  • Traverse from 0 to N-1
  • Initialize searchKey = sum – A[i]
  • If(binarySearch(searchKey, A, i + 1, N) == True     
  • Return True
  • Return False


Algorithm,


function binarySearch( arr,  low,  high,  searchKey)

{

 

    while (low <= high) {

        let m = low + (high - low) / 2;

 

        // Check if searchKey is present at mid

        if (arr[m] == searchKey)

            return true;

 

        // If searchKey greater, ignore left half

        if (arr[m] < searchKey)

            low = m + 1;

 

        // If searchKey is smaller, ignore right half

        else

            high = m - 1;

    }

 

    // if we reach here, then element was

    // not present

    return false;

}

 

const checkTwoSum = ( arr, sum) => {

     

    /* Sort the elements */

    arr.sort();

 

    // Traversing all element in an array search for

    // searchKey

    for (let i = 0; i < arr.length - 1; i++) {

 

        let searchKey = sum - arr[i];

        // calling binarySearch function

        if (binarySearch(arr, i + 1, arr.length - 1, searchKey) == true) {

            return true;

        }

    }

    return false;

}

 


console.log(checkTwoSum([ 1, 4, 45, 6, 10, -8 ],14));

// true


Time complexity: O(N * log N) 
Auxiliary Space: O(1)

I hope you understood the algorithm, if you have any doubts let us know in the comments.