Booleans

3) Suppose you are given an integer array xs that is sorted in ascending order and you are asked to check whether any pair of numbers on xs adds up to a number n. One fast way to first check the sum of the smallest and largest numbers, and then

if this sum is correct, the search has succeeded;

if it is too small, the smallest number can be excluded from the search;

if it is too large, the largest number can be excluded.

In the latter two cases, the search continues with the rest of the array. The search fails if/when only one array element remains.

Write the following method that implements this process.

// returns true iff two numbers on xs sum to n

// assumes that xs is sorted in ascending order

public boolean twoSum(int[] xs, int n)

For example, twoSum({1,4,6,8,9}, 12) should return true, and twoSum({1,4,6,8,9}, 11) should return false.