### Find two elements from an array whose sum equals a given element timecomplexity linearithmictime array searching    Posted: 5 years ago Updated: 3 years ago Edit answers (2) views (7057)

Suppose you are given an array of n integers. You are asked to determine whether there exists two elements whose sum is exactly equal to another given integer x . Can you describe a $$\theta(nlogn)$$ time algorithm?

 Posted: 3 years ago Updated: 3 years ago 0 8 Edit void find_split(int a[], int arr_size,int number){ int i,j = 0, first; int num1 = 0, num2 = 0; while (j != arr_size) { for(i =0; i < arr_size ; i++) { first = a[j]; if ((first + a[i]) == number) { num1 = first; num2 = a[i]; } } j++; } printf("Both the numbers are %d and %d",num1,num2);} Posted: 5 years ago 1 0 Edit The algorithm will be : Sort the array. Take the first element of the array and do binary search to find ( x - first element) in the array. If ( x - first element) is found, return true. Else, repeat the binary search for the rest of the elements in the array. If all the searches result false, return false. Running time for merge sort is $$\theta(nlogn)$$. Running time for each binary search is $$O(logn)$$. So, running time for binary search of $$(n-1)$$ elements is $$O(nlogn)$$. Therefore, total running time is $$\theta(nlogn) + O(nlogn) = \theta(nlogn)$$.public static boolean search2Numbers (int[] array, int x){ /* Sort the array */ Arrays.sort (array); /* Index of first element */ int i = 0; /* Index of last element */ int j = array.length - 1; while (i < j) { /* Check if the sum of the elements at index i and j equals x */ if (array[i] + array[j] == x) return true; /* If the sum is greater than x, decrease the sum */ elseif (array[i] + array[j] > x) j--; /* If the sum is less than x, increase the sum */ else i++; } /* If there is no such pair */ return false; }