I need to find the n-th smallest value in an unsorted array, without sorting it of course. The function needs to be recursive. I thought about the code below but that doesn't work, because I can miss some of the values in the small arrays. any suggestions ?

Examples:

array ={5,2,10,11,18,3,7,9,15,17}
index = 3
expected return = 7
    
index=7
expected return = 15

int func(int arr[], int size, int index)
{
  //if we cant divide the array anymore
  if (size == 1)
    return arr[0];

  //if we don't need to divide the array anymore
  if (index == 1)
    return findMinInArr(arr, size);

  //split the array to 2 arrays and work on lower level
  return Max(func(arr, size / 2, index / 2), func(arr   size / 2, size - size / 2, index - index / 2));

}

CodePudding user response：

Your approach fails because there is no reason for the partition into halves to be meaningful w.r.t. finding your value of interest.

For example, suppose you need the 2nd smallest value. It could be the case that the smallest and second-smallest values are both in the first half of the array; and the second half only has very large values. Your use of Max() will result in your function returning one of these values.

Instead, consider:

1. If the values are all distinct, implementing a function to find the smallest value that's no smaller than a given value, and using that as a building-block.

2. Partially-sorting the array, using one of the sorting algorithms you have likely learned about already.

These are hints, as I suspect you're asking us about a "homework question" and you should make the effort to solve it on your own.

CodePudding user response：

I believe you are going in the wrong way, trying to divide your array.

I would like to replace the smallest number in your array by INT_MAX, so the idea is to do something like (pseudo-code):

int get_smallest(array, index)
{
  if index==0 
  then return smallest(array);
  else
  {
    replace_smallest_number_by_INT_MAX(array);
    return get_smallest(array, index - 1);
  }
}

So, when you run this, you would have a behaviour like this:

  get_smallest({5      , 2      , 10, 11, 18, 3      , 7, 9, 15, 17}, 3)
= get_smallest({5      , INT_MAX, 10, 11, 18, 3      , 7, 9, 15, 17}, 2)
= get_smallest({5      , INT_MAX, 10, 11, 18, INT_MAX, 7, 9, 15, 17}, 1)
= get_smallest({INT_MAX, INT_MAX, 10, 11, 18, INT_MAX, 7, 9, 15, 17}, 0)
= 7