I need to write a program which decides if there are two integers a and b in a given list such that a + b = c. The input would be a list and the integer c. It could be the case, that a == b, but a must appear two times in the list in that case. The run time must be in O(n*log(n)).
I have tried to implement a binary search, but since the list must be sorted for that, it is not going to work if the list is not sorted because the sorting would take at least O(n*log(n)) time. I am trying to implement merge sort without merging at the end, and just getting a and b, but I don't know if it is a dead end. What would be your way to even get started? It's really important that run time is not above O(n*log(n)).
Sorting in-place can be done in O(n log(n)) time. The subsequent search can also be done in O(n) time, resulting in a total of O(n log(n)). Once the data is sorted, for each element a of the array, check if c - a is also in the array using a simultaneous search from the other end. You will traverse the entire array exactly once that way. This approach is suggested by @RockyLi. It has the advantage of using O(1) additional memory: the input list needs to be sorted in-place.
If using O(n) additional memory is acceptable, you can follow @PatrickHaugh's suggestion. Create a set. Add every element, a, in the list to the set. If c - a is already in the set, return True. This requires O(n) time to complete (a single pass), and no sorting. But it will likely more than double the amount of memory you use.
Here are toy implementations:
O(1) space, O(n log(n)) time
def has_sum(lst, c):
lst.sort()
rev = reversed(lst)
end = next(rev)
for item in lst:
while end > c - item:
end = next(rev)
if end == c - item:
return True
if item > end:
return False
O(n) space, O(n) time
def has_sum(lst, c):
found = set()
for item in lst:
if c - item in found:
return True
found.add(item)
return False