Median is just a special case of searching for k-th element. For today, let’s just focus on arrays with distinct elements, hence each value needs to be unique.

While straightforward solution would be to sort the array in O(n.log(n)) and pick k-th position in O(1), we can do…