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?
void find_split(int a[], int arr_size,int number) |
The algorithm will be :
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){ |