Finding if two elements in a pre-sorted array sum to equal a certain value
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.开发者_C百科 If anyone could give me some pointers on what I might be missing it would be appreciated.
Start at the first element, and go sequentially. While that, search for the second element using binary search.
Because they are pre sorted you can use a binary search and a linear search
精彩评论