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.

@letsc: use two indexes a and b; initialize with a=1 and b=n. Check sum of elements at indexes a and b. If the sum is your target, stop, you found the elements. If the sum is lower, increase a; if it's lower, decrease b. When a=b, stop, there are no elements matching. Because the elements are sorted, you'll only skip pairs which you know aren't candidates. — Joubarc
– Joubarc, Commented Jul 4, 2012 at 14:30

Khaled Alshaya · Accepted Answer · 2010-02-05 01:31:01Z

4

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

answered Feb 5, 2010 at 1:31

Khaled Alshaya

97.5k41 gold badges183 silver badges238 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

JohnT Over a year ago

Thanks. I can't believe I missed that.

John Boker · Accepted Answer · 2010-02-05 01:31:22Z

0

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

answered Feb 5, 2010 at 1:31

John Boker

83.8k17 gold badges101 silver badges130 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related