Finding minimum number in an array with recursion

Question

when i dissect the logic of my code, it makes sense to me and looks like it should work. I need to find and return the smallest number in an array using recursion. here is my code

public static int findMin(int[] numbers, int start, int last)
{
    int min = numbers[start]; // sets first value in array to minimum

    if(numbers[start]<numbers[last]&& numbers[start]<min)
    {   // if 1st value < last value in array and 1st value smaller than min, set min to first value
        min = numbers[start];

    }
    else if(numbers[start]>numbers[last]&& numbers[last] < min)
    {   // if 1st value > last value and last value < min, set min to last value
        min = numbers[last];
    }
    else
    {   // if 1st and last value are equal returns 1st value
        return numbers[start];
    }
        // recursively calls... or not
    findMin(numbers, start+1, last-1);
    return min;
}

inputs used are 33 -55, -44, 12312, 2778, -3, -2, 53211, -1, 44, 0

output getting:

The minimum number is 0 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at Assignment9.countEven(Assignment9.java:72) at Assignment9.countEven(Assignment9.java:87) at Assignment9.main(Assignment9.java:34)

Expected: -55

i am assuming my recursive call is incorrectly placed. Please help, thank you.

dreamcrash · Answer 1 · 2016-04-01T17:38:27.497

This should do the trick

public static int findMin(int[] numbers, int start, int last)
{
    if(start == last) return numbers[0];
    return Math.min(numbers[start],findMin(numbers, start+1, last));
}

If for some reason you cannot use the Math.min you can always use:

public static int findMin(int[] numbers, int start, int last)
{
    if(start == last) return numbers[0];

    int min = findMin(numbers, start+1, last);

    return  (numbers[start] <= min) ? numbers[start] : min;
}

The major problems with or solution are:

-> you are not correctly checking the stop case;

-> you are not using the min value calculated in each recursive call;

-> and you are not checking for the cases that you go over the array limits.

score 0 · Answer 2 · answered Apr 01 '16 at 17:24

First glance, it looks like you are not saving the result from your recursive call, you're just calling it as if it was a void method.

Instead of

findMin(numbers, start+1, last-1);
return min;

Try:

min = findMin(numbers, start+1, last-1);
return min;

justAbit · Answer 3 · 2016-04-01T17:54:19.813

0

Why don't you simple try this:

    public static int  findMin(int[] numbers, int start, int last) {
        if(start == last){
            return numbers[start];
        }

        if(numbers[start] <= numbers[last]) {
            last -= 1;
        } else {
            start += 1;
        }

        return findMin(numbers, start, last);
    }

OR you can use Divide and Conquer strategy as suggested by Qriss:

    public static int findMin(int[] numbers){
        return findMinHelper(numbers, 0, numbers.length);
    }

    public static int findMinHelper(int[] numbers, int left, int right){
        int min1 = 0, min2 = 0;

        if (left == right - 1){
            return numbers[left];
        } else {
              min1 = findMinHelper(numbers, left, (right + left) / 2);
              min2 = findMinHelper(numbers, (right + left) / 2, right);
        }

        return (min1 < min2) ?  min1 : min2;
    }

edited Apr 01 '16 at 17:54

answered Apr 01 '16 at 17:32

justAbit

4,226
2
19
34

nice, but if (left == right - 1) you still need to return the smaller one of number[left] and numbers[right] – Turo Apr 01 '16 at 18:56
Does that really matter? If (left == right - 1) both indexes will be pointing to the same element in array, wouldn't it? – justAbit Apr 02 '16 at 05:27
it does matter because they do point to neighboured elements, run with -55, -33, -66 and you'll get -55 – Turo Apr 02 '16 at 07:21
Still I don't see your point. Just to clarify, when `right` is passed in recursion, it's actually `length` of `numbers`, not last index of the array. Besides, I tried to run the code with your input as well and it returns -66 – justAbit Apr 02 '16 at 14:28
Ah sorry, i missed that with length, that did the trick, together with the doubke checking of the position in the middle: i.E. you call findMinHelper(numbers,0,1) and findMinHelper(1,2), which corrects the possible wrong answer of findMinHelper(numbers,0,1), when numbers[1] smaller than numbers[0]. But with that you have unnessarily more comparisons. – Turo Apr 02 '16 at 15:31

Finding minimum number in an array with recursion

3 Answers3