Function returning the wrong kth value while using sets-CodePudding

I was attempting to solve this question on some website where you have the find the kth smallest value in c so I came up with:


#include <bits/stdc  .h>
using namespace std;
int kthSmallest(int arr[], int l, int r, int k) {

    // l is the first index 
    // r is the index of the last element (size - 1)
    // k is the kth smallest value 
    set<int> s(arr, arr   r); 

    
    set<int>:: iterator itr = s.begin();
    advance(itr, (k - 1));
    
    return *itr;
}
int main() {
  int arr[] = {7, 10, 4, 20, 15};
  cout << kthSmallest(arr, 0, 4, 4);
  return 0;
}

This shows the output of 20 instead of 15 which is the right answer and I cannot figure out what I did wrong here.

CodePudding user response：

The 2nd argument of the constructor of std::set should be an iterator for an element next to the last element, not one for the last element.

Therefore, you are operating with a set whose members are {7, 10, 4, 20}.

The line

set<int> s(arr, arr   r);

should be

set<int> s(arr, arr   r   1);

or (to match the comment)

set<int> s(arr   l, arr   r   1);

CodePudding user response：

The range in this statement

set<int> s(arr, arr   r);

is specified incorrectly when r is equal to 4 for this array

int arr[] = {7, 10, 4, 20, 15};

that has 5 elements. It means that 15 is not present in the range [7, 10, 4, 20]. You have to specify the parameter r equal to 5 that is to the number of elements in the array instead of 4.

Also the parameter l is not used in the function.

And you need to check whether the value of k is not greater than the value of r calling the function std::advance.

Also pay attention to that the array can have duplicated values. In this case the function can return an incorrect value.

So in general your function is incorrect and unsafe.

Instead of returning an object of the type int you should return either an iterator that points to the target object in the array or to the end of the range or the index of the target element..

With your approach you should use std::multiset instead of std::set. And the value of k should start from 0 as all indices in C . Otherwise calling the function with the value of k equal to 0 you will get undefined behavior.

Here is a demonstration program.

#include <iostream>
#include <functional>
#include <set>
#include <iterator>

size_t kthSmallest( const int arr[], size_t n, size_t k ) 
{
    if ( not ( k < n ) ) return n;

    std::multiset<std::reference_wrapper<const int>> s;

    for ( size_t i = 0; i < n; i   )
    {
        s.insert( std::ref( arr[i]) );
    }

    auto it = std::next( std::begin( s ), k );

    size_t result = std::distance( arr, &it->get() );

    return result;
}    

int main() 
{
    int arr[] = {7, 10, 4, 20, 15};
    const size_t N = sizeof( arr ) / sizeof( *arr );

    for ( size_t i = 0; i < N; i   )
    {
        std::cout << i << ": " << arr[kthSmallest( arr, N, i )] << '\n';
    }

    return 0;
}

The program output is