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)

## 0 Comments