Finding if two elements in a pre-sorted array sum to equal a certain value

Question

I'm working on a homework problem and I'm having some difficulties creating a O(n*logn) solution. I need to write a function that takes a pre-sorted array and a value to search for. I then need to find if any two elements of the array sum to equal that value.

I need to create both O(n) and O(n*logn) algorithms for this.

The O(n) was easy to create; however, I am having difficulties creating the O(n*logn) algorithm without adding in some gratuitous code that doesn't actually help in solving the problem. If anyone could give me some pointers on what I might be missing it would be appreciated.

Answer 1

Start at the first element, and go sequentially. While that, search for the second element using binary search.

Answer 2

Because they are pre sorted you can use a binary search and a linear search