FINALLY! a self explained solution (binary search solution - no sort)


#1
kthsmallest : function(A, B){
        // find the min and max of A
        let low = 0;
        let max = 0;
        let res = 0;
        for(let i=0; i<A.length; i++) { max = Math.max(max, A[i]); }
        
        // each iteration "guess" the kth smallest element (mid) and check how many
        // elements in A are equal/less/greater than mid.
        while(low <= max) {
            const mid = Math.floor((low+max)/2)
            let lt = 0;
            let eq = 0;
            let gt = 0;
            for(let i=0; i<A.length; i++) {
                if(A[i] < mid) { lt++; }
                else if(A[i] > mid) { gt++; }
                else { eq++; }
            }
            if(lt < B) {
                // the number of less than mid elements is less than B
                if(lt+eq >= B) {
                    // this means that mid satisfy all conditions
                    // (still need to find the closes element to mid in A)
                    low = mid;
                    break;
                }
                low = mid+1;
            } else {
                // mid is too low - need to check greater numbers
                max = mid-1;
            }
        }
        // find the closest number in A (!) which is the closest to mid
        for(let i=0; i<A.length; i++) {
            if(A[i] <= low) {
                res = Math.max(res, A[i]);
            }
        }
        return res;
    }