Kth smallest element (Binary Search)

Revision en2, by iamskp, 2020-10-10 19:34:53

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English iamskp 2020-10-10 19:34:53 333
en1 English iamskp 2020-10-10 19:33:29 1159 Initial revision (published)