CODEWITHSUNDEEP
algorithm
JohnT
JohnT

Reputation: 53

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. If anyone could give me some pointers on what I might be missing it would be appreciated.

Upvotes: 5

Views: 1501

Answers (2)

John Boker
John Boker

Reputation: 83699

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

Upvotes: 0

Khaled Alshaya
Khaled Alshaya

Reputation: 96849

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

Upvotes: 4

Related Questions