Description
Textbooks for References:
[1] CLRS
1. Given an array A of n numbers, a query x, and a number k,
find the k numbers in A that are closest (in value) to x.
For example:
find([4,1,3,2,7,4], 5.2, 2) returns [4,4]
find([4,1,3,2,7,4], 6.5, 3) returns [4,7,4]
find([5,3,4,1,6,3], 3.5, 2) returns [3,4]
Filename: closest_unsorted.py
Must run in O(n) time.
The elements in the returned list must be in the original order.
In case two numbers are equally close to x, choose the earlier one.
2. [WILL BE GRADED]
Now what if the input array is sorted? Can you do it faster?
find([1,2,3,4,4,7], 5.2, 2) returns [4,4]
find([1,2,3,4,4,7], 6.5, 3) returns [4,4,7]
Filename: closest_sorted.py
Must run in O(logn + k) time.
The elements in the returned list must be in the original order.
Note: in case two numbers are equally close to x, choose the smaller one:
find([1,2,3,4,4,6,6], 5, 3) returns [4,4,6]
find([1,2,3,4,4,5,6], 4, 5) returns [2,3,4,4,5]
Hint: you can use Python’s bisect.bisect for binary search.
3. For a given array A of n *distinct* numbers, find all triples (x,y,z)
s.t. x + y = z. (x, y, z are distinct numbers)
e.g.,
find([1, 4, 2, 3, 5]) returns [(1,3,4), (1,2,3), (1,4,5), (2,3,5)]
Note that:
1) no duplicates in the input array
2) you can choose any arbitrary order for triples in the returned list.
Filename: xyz.py
Must run in O(n^2) time.
Hint: you can use any built-in sort in Python.
