Binary search lets us also tackle this issue. Searching element in sorted array will take O(log(n)) time as we know it. First we arrange the array. After that, for every number arr[i] in the array, we first find its complement—that is, target less current number—then apply binary search to rapidly explore the subarray following index i for this complement. We return false if we never discover a complement (after looking over all the numbers); we return true if we do find the complement.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to perform binary search
bool binarySearch(vector<int> &arr, int left, int right, int target){
while (left <= right){
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return true;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
// Function to check whether any pair exists
// whose sum is equal to the given target value
bool twoSum(vector<int> &arr, int target){
// Sort the array
sort(arr.begin(), arr.end());
// Iterate through each element in the array
for (int i = 0; i < arr.size(); i++){
int complement = target - arr[i];
// Use binary search to find the complement
if (binarySearch(arr, i + 1, arr.size() - 1, complement))
return true;
}
// If no pair is found
return false;
}
int main(){
vector<int> arr = {0, -1, 2, -3, 1};
int target = -2;
// Call the twoSum function and print the result
if (twoSum(arr, target))
cout << "true";
else
cout << "false";
return 0;
}C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// Comparison function for qsort
int compare(const void *a, const void *b){
return (*(int *)a - *(int *)b);
}
// Function to perform binary search
bool binarySearch(int arr[], int left, int right, int target){
while (left <= right){
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return true;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
// Function to check whether any pair exists
// whose sum is equal to the given target value
bool twoSum(int arr[], int n, int target){
// Sort the array
qsort(arr, n, sizeof(int), compare);
// Iterate through each element in the array
for (int i = 0; i < n; i++){
int complement = target - arr[i];
// Use binary search to find the complement
if (binarySearch(arr, i + 1, n - 1, complement))
return true;
}
// If no pair is found
return false;
}
int main(){
int arr[] = {0, -1, 2, -3, 1};
int target = -2;
int n = sizeof(arr) / sizeof(arr[0]);
// Call the twoSum function and print the result
if (twoSum(arr, n, target))
printf("true\n");
else
printf("false\n");
return 0;
}Java
import java.util.Arrays;
class GfG {
// Function to perform binary search
static boolean binarySearch(int[] arr, int left,
int right, int target){
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return true;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
// Function to check whether any pair exists
// whose sum is equal to the given target value
static boolean twoSum(int[] arr, int target){
// Sort the array
Arrays.sort(arr);
// Iterate through each element in the array
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
// Use binary search to find the complement
if (binarySearch(arr, i + 1, arr.length - 1,
complement))
return true;
}
// If no pair is found
return false;
}
public static void main(String[] args){
int[] arr = { 0, -1, 2, -3, 1 };
int target = -2;
// Call the twoSum function and print the result
if (twoSum(arr, target)) {
System.out.println("true");
}
else {
System.out.println("false");
}
}
}Python
# Function to perform binary search
def binary_search(arr, left, right, target):
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
# Function to check whether any pair exists
# whose sum is equal to the given target value
def two_sum(arr, target):
# Sort the array
arr.sort()
# Iterate through each element in the array
for i in range(len(arr)):
complement = target - arr[i]
# Use binary search to find the complement
if binary_search(arr, i + 1, len(arr) - 1, complement):
return True
# If no pair is found
return False
arr = [0, -1, 2, -3, 1]
target = -2
# Call the two_sum function and print the result
if two_sum(arr, target):
print("true")
else:
print("false")JS
// Function to perform binary search
function binarySearch(arr, left, right, target) {
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (arr[mid] === target)
return true;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
// Function to check whether any pair exists
// whose sum is equal to the given target value
function twoSum(arr, target) {
// Sort the array
arr.sort((a, b) => a - b);
// Iterate through each element in the array
for (let i = 0; i < arr.length; i++) {
let complement = target - arr[i];
// Use binary search to find the complement
if (binarySearch(arr, i + 1, arr.length - 1, complement))
return true;
}
// If no pair is found
return false;
}
let arr = [0, -1, 2, -3, 1];
let target = -2;
// Call the twoSum function and print the result
if (twoSum(arr, target)) {
console.log("true");
} else {
console.log("false");
}Output
1
Time Complexity: O(n*log(n)), for sorting the array
Auxiliary Space: O(1)