Minor observation regarding 22.17

#1

This is extremely minor, but since I really enjoyed problem 22.17 (K Elements Closest to the Median) I thought I would mention it. Would it be possible to replace:

nth_element(A->begin(), target - 1, A->end());

with:

nth_element(A->begin(), target - 1, target);

for the even number of elements case? I think the first call would ensure the desired element is in the left half of the array.

0 Likes
#2

Hey Michael,

Great, it is a very neat observation, and you are right, there is no reason to include the right part during the next call of nth_element(). However, I would like to keep this still for readability as well as this won’t improve the time complexity.

Again, thanks for this idea and you definitely understand thr property of selection algorithm very well. Good job!

0 Likes