Following all instruction | Worst case complexity O(N^2) | average case complexity smaller than O(N^2)


#1
int Solution::kthsmallest(const vector<int> &A, int B) {
int lowerBound=INT_MIN;
int upperBound=INT_MAX;
int i=A.size()-1;
int chk=A[i];
int lower=0;
int same=0;
for(int j=0;j<A.size();j++){
    if(A[j]<chk)lower++;
    else if(A[j]==chk)same++;
}
if(lower<B &&(lower+same)>=B){
    return chk;
}
else if(lower>=B){
     upperBound=chk;
}
else{
    lowerBound=chk;
}

for(i=0;i<A.size();i++){
    if(A[i]>=upperBound || A[i]<=lowerBound){
        
    }
    else{
        lower=0;
        same=0;
        for(int j=0;j<A.size();j++){
            if(A[j]<A[i]) lower++;
            else if(A[j]==A[i])same++;
        }
        if(lower<B && (lower+same)>=B){
            return A[i];
        }
        else if(lower>=B){
            if(A[i]<upperBound) upperBound=A[i];
        }
        else{
            if(A[i]>lowerBound)lowerBound=A[i];
        }
    }
}

}