Describe a (nlgn)-time algorithm that, given a set S of n integers and another i

Question

Describe a (nlgn)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

Does this answer complete the question asked above? It doesn't quite look good to me. Please, I really need help with this.

So, we can sort the array with merge sort (runs at e(nlg n) time) and then for each element Sil in the array, we can do a binary search for z Si on the sorted array (this will again run at O(n lgn) time). So, the overall algorithm will also run at O(n lg n) time. Pseudo-code for sUM SEARCH (s, n, x) MERGE-SORT(S 1, n) 2 for i 1 to n if BINARY-SEARCH (S, x S[i]) NIL return true return false See chapter text for pseudocode for MERGE-soRT and Exercise 2.3-5 for BINARY-SEARCH (we can use either of iterative and recursive binary search) This problem can be solved in another way which still uses a O(n lgn) sorting procedure but we can simplify the searching procedure to reduce the contstants in the runtime complexity Pseudo-code for sUM SEARCH (s, n, x) MERGE-SORT (S 1, n) left 3 right n 1 4 while (left right) if (S [left] S[right] x) return true else if (S[left stright J x) left else 10 right 11 12 13 return false

Explanation / Answer

First should does not work correctly.

But second is correct.

For exmple: arr [] = 1, 2, 3, 4, 5

If sum = 6 then when i = 2, arr[2] = 3, if you search using binary seach (6-3) = 3, then it returns the i, that is index of aar[2]

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.