# Recursive linear search algorithm

2669 views
-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<>();

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

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

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.

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