Understanding Binary Search for Kth Smallest element in an Array

Question

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?

Answer 1

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.