CODEWITHSUNDEEP
javarecursion
user3242607
user3242607

Reputation: 219

trying to find second smallest integer in array recursively java

i'm so lost. I need to find the second smallest integer in an array recursively. I've started to write the method but I know its wrong and don't know where to go from here.

public static int findSecondSmallest(int [] array)
{
    int secSmall = array[0], min = array[0];
    if(array.length >= 1)
    {
        findSecondSmallest(array);
        if(secSmall > min)
            secSmall = array[0+1];
    }

    return secSmall;
}

Upvotes: 0

Views: 2640

Answers (3)

emaneman1011
emaneman1011

Reputation: 1

The trick is smarter pseudocode. This may not be the most efficient algorithm but its stupid smart. also in any case, recursive is not the way to go for such a problem.

secondsmallest(Array of size n)

  if n == 2
     if array[0] < array[1]
         return array[1]
     else return array[2]

 if n not equal 2 then

    remove largest element from the array
    return secondsmallest(newArray of size n-1)

Upvotes: 0

TuanDT
TuanDT

Reputation: 1667

What you could do is to keep track of the smallest one and the second smallest one as you traverse the array from beginning to end. Update them both if you run into something smaller than the second smallest or something bigger than the smallest but less than the second smallest. Hope the following code makes sense:

public class Driver {
    public static int MAX_VAL = 1000000;
    public static void main(String[] args) {
        int[] arr = {2,5,3,6,2,7,43,2,56,2,-1, 1, 5};
        int[] smalls = new int[2];
        int sm = find(arr, 0, smalls);
        System.out.println(sm);
    }

    public static int find(int[] arr, int index, int [] smalls) {
        if(index == 0) {
            smalls[0] = arr[index];
            smalls[1] = Integer.MAX_VALUE;
            find(arr, index+1, smalls);
        } else if(index < arr.length){
            if(arr[index] < smalls[0]){
                smalls[1] = smalls[0];
                smalls[0] = arr[index];
            } else if(smalls[1] > arr[index]) {
                    smalls[1] = arr[index];
            }
            find(arr,index + 1, smalls);
        }
        return smalls[1];
    }
}

Here, index stands for the index of the last element in your 'partial array'. Every recursive step, you examine the first index + 1 elements of your array. Note: small[0] is the SMALLEST element of the partial array and small[1] is the second smallest of the partial array.

For a good treatment of recursion, I recommend you pick up Prolog. This language has no loops and you will rely heavily on recursion.

Upvotes: 2

gandaliter
gandaliter

Reputation: 10101

This is very easy to do iteratively, so a recursive solution is already a bit contrived, and there are several ways to do it. For example you could write a function which recurses on two halves of the array and gives the second smallest of the four numbers returned. I'll assume you want to split off the first element and recurse on the rest of the array.

The recursive function will return both the smallest and the second smallest in an IntPair, the definition of which I omit, so you will need a wrapper function to extract the second smallest from this pair.

public static int findSecondSmallest(int[] array) {
    return findSecondSmallestAndSmallest(0, array).getSecond();
}

private static IntPair recurseSecondSmallest(int index, int[] array) {
    if (array.length - index == 2) {
        if (array[index] < array[index+1])
            return new IntPair(array[index], array[index+1]);
        else return new IntPair(array[index+1], array[index]);
    }
    IntPair recursiveResult = recurseSecondSmallest(index+1, array);
    if (array[index] < recursiveResult.getFirst())
        return new IntPair(array[index], recursiveResult.getFirst());
    else if (array[index] < recursiveResult.getSecond())
        return new IntPair(recursiveResult.getSecond(), array[index]);
    else return recursiveResult;
}

Upvotes: 1

Related Questions