I was doing a problem in which we have to find kth smallest element using constant space and the array is read only. The array can be unsorted.
Link to the problem : https://www.interviewbit.com/problems/kth-smallest-element-in-the-array/
I want to know how the binary search solution works here.
Here is a working code I found:
int Solution::kthsmallest(const vector<int> &A, int B)
{
int maximum = 0;
for(int a : A) maximum = max(maximum, a);
int low = 0, high = maximum;
while(low != high)
{
int mid = (low + high + 1)/2;
int count = 0;
for(int a : A)
{
if(a < mid) count++;
}
if(count < B) low = mid;
else high = mid - 1;
}
return low;
}
Tip: don't think binary search is just a "neat trick" that is useful on arrays from the input that you can sort. You can also apply binary search when there are no obvious arrays.
Let
f(x)
be the number of numbers in the given array that are smaller thanx
. You can calculatef(x)
by just going through each element of the array. You can notice that ifx < y
, thanf(x) <= f(y)
. Why is this true? Well, all the numbers that are smaller thanx
are also smaller thany
andf(y)
will also take into consideration the elements that are >=x
and smaller thany
, if they exist. Sincef(x) <= f(y)
for any numbersx
andy
, such thatx < y
,f
is increasing.Now, you can think of this function
f
as an increasing array and we need to find the indexi
where we havef(i) = k
(or the smallesti
such thatf(i) > k
, in case there is nof(i) = k
). As you can see, we basically now have a usual binary search problem. However, we are not done yet. It is not practical to calculate every single value off
, because the binary search doesn't need all of them. You just need to calculatef(mid)
, wheremid
is the middle position used in the binary search.In fact, you can use binary search on any increasing (or decreasing) function.