CODEWITHSUNDEEP
javalistrecursion
Jonathan Zier
Jonathan Zier

Reputation: 168

Recursive linear search algorithm

I have a homework assignment to create a recursive linear search algorithm from one index to another. For some reason the following code return -1 every time.

public static int recLinearSearch(ArrayList<String> pList, String pKey, int pBeginIdx, int pEndIdx) {
    if (pBeginIdx > pEndIdx) {
        return -1;
    } else if (pList.get(pBeginIdx).equals(pKey)) {
        return pList.indexOf(pBeginIdx);
    }
    // Recursive case
    else return recLinearSearch(pList, pKey, pBeginIdx + 1, pEndIdx - 1);


}

This is how I'm calling it:

ArrayList<String> list = new ArrayList<>();

list.add("Jonathan");
list.add("Zier");

System.out.println(list.size()); // returns 2

int idx = Hw3_1.recLinearSearch(list, "Jonathan", 0, list.size() - 1);
System.out.println(idx);    //returns -1

Upvotes: 2

Views: 1669

Answers (1)

Mureinik
Mureinik

Reputation: 310983

The index isn't an element in the list, so pList.indexOf(pBeginIdx) will always retrun -1. And besides, using indexOf kind of missed the point, IMHO - you're supposed to implement the search yourself. You've correctly checked if the element equals the key - you just need to return it:

public static int recLinearSearch(ArrayList<String> pList, String pKey, int pBeginIdx, int pEndIdx) {
    if (pBeginIdx > pEndIdx) {
        return -1;
    } else if (pList.get(pBeginIdx).equals(pKey)) {
        return pBeginIdx; // Here!
    }
    // Recursive case
    else return recLinearSearch(pList, pKey, pBeginIdx + 1, pEndIdx); // Don't alter the end index!
}

Upvotes: 1

Related Questions