Recursively searching an array

Question

I need to write a piece of code to test whether the unsorted array a contains the value x, anywhere from start to end, inclusive.

This is what I have so far:

boolean linearSearch(int[] a, int x, int start, int end){
  boolean result = false;
  if(a[start]==x){
    result = true;
  } else {
    linearSearch(a,x,++start,end-1);
  }
  return result;
}

This current code throws an array out of bounds exception, and I can't seem to figure out why it's not working. Could anyone possibly give me a nudge in the right direction? Thank you in advance!

Answer 1

Does this work? It seems like it would be much simpler.

boolean linearSearch(int[] a, int x, int start, int end){
    a = Arrays.copyOfRange(a, start, end);
    return Arrays.asList(a).contains(x);
}

Answer 2

The issue you're having is because you're doing insufficient constraint checking. The constraints you need to ensure are:

• That start is less than the length of the array a.
• That end is less than the length of the array a.
• That end is greater than start.

Even given that, your recursion is problematic because of this line:

linearSearch(a,x,++start,end-1);

Every time you recurse into this function, the end value is decremented. That means the original input for end will not actually be the last index checked.

When doing recursion, it is best to think about the base case. In this case, what happens if your array is empty? You must return `false:

boolean linearSearch(int[] a, int x, int start, int end){
  if (a.length == 0) { return false; }
  // Do other things
}

We also need to determine if we are past the end point. This turns out to be the same as the base case:

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  // Do other things
}

Now it's a matter of determining if the head of the array (the first element) is the start position. If not, you skip the check for equality and if so you perform it:

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  if (start <= 0) { //We are within the correct part of the array
     //check for equality
  } // else recurse without checking
}

Checking for equality is just if (head == x):

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  if (start <= 0) { //We are within the correct part of the array
     if (a[0] == x) { return true; }
  } 
  //recurse
}

Now that we have the base cases and equality case checked for, we just have to recurse with the proper variables. Here we can decrement start and end because we are reducing the entire length of the array by one via removal of the head. This decrements the index of every element and also the indices of the start and end. This ensures our base case remains correct.

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  if (start <= 0) { //We are within the correct part of the array
     int head = a[0]; //The head is the first part of an array
     if (head == x) { return true; }
  } 
  // The tail is everything but the head
  int[] tail = Arrays.copyOfRange(a, 1, a.length); //Be careful of off-by-one errors!
  return linearSearch(tail, x, start - 1, end - 1);
}

Lets review our constraints:

• That start is less than the length of the array a.
  • If start is greater than the length of the array, false is returned because we check to ensure the array has some elements in it first. If we have recursed to the point where the array is empty but there is a higher value in start, we will still return.
  • If start is zero or less, we will check the equality condition.
• That end is less than the length of the array a.
  • For the same reason, end will always be less than the end of the array or the found variable. (I'm cheating here a little because it's unclear what the expected behavior is.)
• That end is greater than start.
  • If end is less than start we return false even before start has a chance to be checked.

Naturally, it helps to test, so we package it in a class with a main and put together some useful tests:

import java.util.Arrays;

public class LinearSearch {

    public static boolean linearSearch(int[] a, int x, int start, int end){
        if ((a.length == 0) || (end == 0)) { return false; }
        if (start <= 0) { //We are within the correct part of the array
            int head = a[0]; //The head is the first part of an array
            if (head == x) { return true; }
        }
        // The tail is everything but the head
        int[] tail = Arrays.copyOfRange(a, 1, (a.length)); //Be careful of off-by-one errors!
        return linearSearch(tail, x, start - 1, end - 1);
    }

    public static final void main(String[] args){
        int[] test_arr1 = {1,2,3,4,5};
        int[] test_arr2 = {3,2,3,1,5};
        int[] test_arr3 = {};

        // Basic success test
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 1, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 2, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 3, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 4, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 5, 0, 5));

        // Test that order doesn't matter
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 1, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 2, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 3, 0, 5));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr2, 4, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 5, 0, 5));

        // Test that a sub array works correctly
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 3, 2, 4));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 4, 2, 4));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 1, 2, 4));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 2, 2, 4));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 5, 2, 4));


        // Test empty array
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr3, 3, 1, 2));

        // Test start after finish
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 3, 2, 1));
    }
}

Answer 3

Is the assignment to do it recursively? Because it would be much easier to just do it with a for loop!

But, in terms of determining what is wrong, thinking about doing it with a for loop can help you figure out what your recursive implementation is missing!

for (int i = 0; i < a.length(), i++) {
    boolean result = false;
    if (a[start] == x) {
        result = true;
    }
}
return result;

In the for loop, the middle condition is limiting how many times the loop occurs, which is essentially what you are doing with end. However, you are not actually verifying that end has changed.

End is the same as the length of the array or just some index you want it to stop searching at. Recursively, end is acting as a decrementing count. Once end has decreased to 0, meaning it has checked every element of the array or whatever index you specified to end at.

You need to add an extra conditional to check to see if end == 0 (you've made it through all the elements).

boolean result = false;
if (end == 0) {
    return result;
}
else if (a[start] == x) {
    result = true;
    **return result;**
}
else {
     // do recursive search again
}

Remember to convert your logic to English when you are forming it: "Okay if we've finished searching each element, return. No, okay if we found the element, set result to true and return. Nope, search the next element.

**EDIT: It was pointed out that there was a portion of my answer that was a bit unclear. The out of bounds exception you were receiving was due to you attempting to access an index larger than the length of the array. The solution I provided does not check for this as it assumes the user of the function is providing responsible input to the function.

There are two options for handling this case: 1. Add an extra check in the first conditional (if x is greater than the length of the array minus 1 OR end equals 0) 2. In the method declaration add that it throws an Out of Bounds exception so that the user of the function is responsible for validating their input and the output of the function.

There are many different books and materials that discuss these two options and which should or should not be used. I'll leave that up to you to investigate and decide for yourself.**

Answer 4

why not search the effective way?

boolean linearSearch(int[] a, int x){

    for(int y = 0; y < a.length; y++)
        if(a[y] == x)
            return true;

    return false;
}

And if you want to search within specified bounds (for example search between element 4 and element 8 instead of whole array), you can use this code:

boolean linearSearch(int[] a, int x, int start, int end){

    for(int y = start; y < end; y++)
        if(a[y] == x)
           return true;

    return false;
}

As for your problem,

boolean linearSearch(int[] a, int x, int start, int end){
  boolean result = false;
  if(start == a.length-1)
      return false; // If result still not validated and length limit is reached, return false
  if(a[start] == x){ // When start equals a.length, it throws OFB Exception
    result = true;
  } else{
    linearSearch(a,x,++start,end-1);
  }
  return result;
}