Checking if an array contains an int with recursion and certain limitations

Question

i was given the following problem: create a recursive method that checks if a given array contains a given value. This should be done by splitting the array in two halfes and therfore requires two recursive calls.

The problem for me is that the method head doesnt contain any specifieds index range, that can be altered with recursion, so that every value in the array is searched. I've now tried to just fix the index that is being compared to the value as 0 and continue to split up the array in halfes, so that every value in the array has the index 0 at some point. It doesn't work however and i don't understand why. If anyone could give me a clue as to what i'm doing wrong, that would be helpful, as I'm still very new to java.

My limitations are as follows: no altering of the method head, no global variables, no loops, only classes allowed are: String, Array, Math, Integer.

Example:

int[] array = {2, 4, 7, 10, -10, 4, 0, 0, 27, 11, 4, 6};

System.out.println(containsValue(array4, 11)); This should be true, in my code it is however false.

Code:

private static boolean containsValue(int[] workArray, int value) {

    int count = 0;
    boolean hasValue;

    if (workArray.length > 1) {
        int[] firstHalfArray = Arrays.copyOfRange(workArray, 0, (workArray.length / 2) - 1);
        if (firstHalfArray[count] == value) {
            hasValue = true;
            return containsValue(firstHalfArray, value) || hasValue;
        }
    }

    if (workArray.length > 1) {
        int[] secondHalfArray = Arrays.copyOfRange(workArray, 6, workArray.length - 1);
        if (secondHalfArray[count] == value) {
            hasValue = true;
            return containsValue(secondHalfArray, value) || hasValue;
        }

    }

    return false;

}


public static void main(String[] args) {

    int[] array4 = {2, 4, 7, 10, -10, 4, 0, 0, 27, 11, 4, 6};
    System.out.println(containsValue(array4, 11));
    System.out.println(containsValue(array4, 2));
    System.out.println(containsValue(array4, 25));
    System.out.println(containsValue(array4, 0));
    System.out.println(containsValue(array4, 14));
    System.out.println(containsValue(array4, 6));
}

Thanks in advance

Update: I have tuned and adjusted my code. My base case was horribly wrong, thanks for that. The rest of it still isnt working the way i want it to, even though for my the recursion is correctly implemented (I still continue to split it in half until the base case is reached (workArray.lenght == 1) and the check if that single int in the array is equal to value. What am I still doing wrong?

private static boolean containsValue(int[] workArray, int value) {

        int count = 0;

        if (workArray.length > 1) {
            int[] firstHalfArray = Arrays.copyOfRange(workArray, 0, (workArray.length / 2));
            return containsValue(firstHalfArray, value);
        }

        if (workArray.length > 1) {
            int[] secondHalfArray = Arrays.copyOfRange(workArray, workArray/2, workArray.length - 1);
            return containsValue(secondHalfArray, value);
        }

        if (workArray[count] == value) {
            return true;
        }
        return false;

The problem for me is that the method head doesnt contain any specifieds index range, that can be altered with recursion: then create another recursive method, and call that other method with 0, array.length as arguments. Your method has an obvious bug: if the array only has one element, it always returns false. — JB Nizet
– JB Nizet, Commented Nov 24, 2019 at 19:21
The idea of recursive subdivision is to check the base case to see if you can solve it trivially. Here look for a list of 1 element and return that. Otherwise split the array in 2 and recur on each half (be careful a half doesn't have length 0). For this have a look at List.subList(). This method needs only constant space and time. docs.oracle.com/javase/8/docs/api/java/util/… — Gene
– Gene, Commented Nov 24, 2019 at 19:23
Again, your base case (an array with only one element), is wrongly implemented: it always returns false. For all the other cases, you should split the array in two and return true if one of the two subarrays contain the number. Your hasValue variable shouldn't be there. — JB Nizet
– JB Nizet, Commented Nov 24, 2019 at 19:25
@gurioso agreed, but then a recursive approach is absurd: if multiple copies of the array are done (using hidden loops), you'd better just iterate over the array. I understand that this is just to learn, but the restriction of not being allowed to create a method ruins the point of using recursion. — JB Nizet
– JB Nizet, Commented Nov 24, 2019 at 19:29

Wai Ha Lee · Accepted Answer · 2019-11-25 00:25:34Z

2

I don't understand

why you need this recursion here at all
why you copy the array subsets ... it is better to keep search range in method parameters containsValue(int[] workArray, int value, int startindex, int endidex)

last attribute in copyOfRange is end index but exclusively

private static boolean containsValue(int[] workArray, int value) {

    if (workArray.length == 0) return false;
    if (workArray[0] == value) return true;
    if (workArray.length == 1) return false;

    int middle = workArray.length / 2;

    int[] firstHalfArray = Arrays.copyOfRange(workArray, 0, middle);
    if(containsValue(firstHalfArray, value)) return true;
    int[] secondHalfArray = Arrays.copyOfRange(workArray, middle, workArray.length);
    return containsValue(secondHalfArray, value);

}

edited Nov 25, 2019 at 0:25

Wai Ha Lee

8,856102 gold badges61 silver badges100 bronze badges

answered Nov 24, 2019 at 20:49

Anton Straka

1392 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

CtrlShiftEscape Over a year ago

Using recursion is required on this one, as per specifiction of this task. Thank your for the solution

Collectives™ on Stack Overflow

Checking if an array contains an int with recursion and certain limitations

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related