The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 cause we needed to adjust the mid value based on the start and end of our range. The thing I just can't seem to wrap my head around is why does it work? The numbers in the array are unsorted and not contiguous,duplicates may exist so why does reducing the search space in our range based on countless or countequal give us the correct answer? Can someone give some intuition or simple explanation to why this works?

  • $\begingroup$ Prima facia, binary search does not work for unsorted lists. Are you saying it DOES work? If so, I would like to reproduce it and examine it. I think someone is neglecting the fact of "unsorted". $\endgroup$ – dcromley Jun 30 '18 at 16:17
  • $\begingroup$ @dcromley Binary search is performed on the set of possible values of elements in the array. See my answer. $\endgroup$ – Yuval Filmus Jun 30 '18 at 16:32
  • $\begingroup$ @Yuval Filmus Looking at YF's answer, he has a 2nd array B, which is, like, cheating. If array A is [ 1003, 1002, 1001 ], and B[i] is the number of elements in A which are at most i, we have B = [ 0, 0, 0 ]. ? $\endgroup$ – dcromley Jun 30 '18 at 22:42
  • 1
    $\begingroup$ @dcromley Read my answer more carefully, focusing on the yellow stuff. $\endgroup$ – Yuval Filmus Jun 30 '18 at 22:44

Let me start by recalling the question:

Given an unsorted array of $n$ elements in the range $1,\ldots,m$, find the $k$th smallest element in $O(n\log m)$ time and $O(1)$ case.

Calling the array $A$, the idea is to perform binary search on the array $B$ of length $m$ in which $B[i]$ is the number of elements in $A$ which are at most $i$. If $B[i] \geq k$ but $B[i-1] < k$ (assuming $B[0] = 0$), then $i$ is the $k$th smallest element. We can find $i$ using binary search.

Instead of computing the array $B$ ahead of time, we have "oracle access" to it: we can compute any given entry in time $O(n)$ by going over the entire array $A$. This is the algorithm you link to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.