Recursive linear search algorithm

2669 views java
-1

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

answered question

I think return pList.indexOf(pBeginIdx); should just be return pBeginIdx;. Otherwise, you're looking for an Integer in a list of String objects. I've VTC'ed this as a typo - that seemed a better fit than posting an answer.

@DawoodibnKareem is correct(ish). Since you don't say if the function should return an index or the element, return pList.get(pBeginIdx) may be correct. The main problem is you're modifying both end points, but only testing one.

Now that I see it it's a really stupid mistake. Thank you!

I've removed my close vote, since this was caused by two errors - the one I mentioned and the one Tibrogargan mentioned.

how do you use pEndIdx? it seems there is no use for that and on each matching, it decrements for no reason.

1 Answer

2

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!
}

posted this

Have an answer?

JD

Please login first before posting an answer.