Question: Suppose you have a sorted array of positive and negative integers and would like to determine if there exist some value x such that both x and -x are in the array. Consider the following three algorithms:
Algorithm #1: For each element in the array, do a sequential search to see if its negative is also in the array.
Algorithm #2: For each element in the array, do a binary search to see if its negative is also in the array.
Algorithm #3: Maintain two indices i and j, initialized to the first and last element in the array, respectively. If the two elements being indexed sum to 0, then x has been found. Otherwise, if the sum is smaller than 0, advance i; if the sum is larger than 0 retreat j, and repeatedly test the sum until either x is found, or i and j meet. Determine the running times of each algorithm, and implement all three obtaining actual timing data for various values of N. Confirm your analysis with the timing data.