Ok, first off I want to state that this is NOT a homework question! I'm wading through an algorithm book that I bought (pleasure reading if you can believe it!) and I'm having difficulty figuring out one of the problems in it, one of those star problems that are supposed to be harder than the rest. This question is only in chapter 3, so it shouldn't take a very high level algorithm. What the question asks for is given an unsorted array of n integers, and a value x, write an algorithm that tells you whether or not there exists two integers in the array who's sum is EXACTLY x.
No problem, just iterate through the array with two nested loops that checks every possible configuration right? Nope, this sucker needs to run at a worst case (n log n) time which usually means something recursive/divide and conquer needs to be done. Straight iteration runs at n^2 time. I can't figure out how to do this.
The best I can figure is to first recursively merge sort the array which is (n log n) time, then iterate through the array from the beginning and using divide and conquer to see if (x-array[i]) exists. This should be faster than the straight iteration, but I feel like there must be a better way since my algorithm has three separate functions, 2 at (n log n) time and one at n time. Anyone have any ideas?
Sorry so confusing, if any of this needs clarification, don't hesitate to ask!
