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;
}