CODEWITHSUNDEEP
javarecursiondata-structuresrecursive-datastructureslinear-search
jumpman8947
jumpman8947

Reputation: 437

Linear Search Recursive Last Occurrence

I'm trying to perform a linear search on an array where it finds the last occurrence of a target. I'm stuck because my search is only finding the first occurrence of the target not the last. 

/** Recursive linear search that finds last occurrence of a target in the array not the first
 * 
 * @param items The array
 * @param target the item being searched for
 * @param cur current index
 * @param currentLength The current length of the array
 * @return The position of the last occurrence
 */
public static int lineSearchLast(Object[] items, Object target, int cur, int currentLength){
    if(currentLength == items.length+1)
        return -1;
    else if (target.equals(items[cur])&& cur < currentLength)
        return cur;
    else
        return lineSearchLast(items, target, cur +1, currentLength);
}

public static void main (String[] args){
Integer[] numbers5 = {1,2,4,4,4};
int myResult = lineSearchLast(numbers5, 4, 0, 5);
System.out.println(myResult);

Upvotes: 1

Views: 1832

Answers (1)

Mshnik
Mshnik

Reputation: 7032

You shouldn't need two index arguments - one (a current index) should do the trick. Moreover, to make sure that you find the last equivalent element first, it's prudent to start at the back and work forward.

/** Returns the index of the last occurance of target in items */
public static int findLastOccurance(Object[] items, Object target){
    return findLastOccurance(items, target, items.length - 1);
}

/** Helper method for findLastOccurance(items, target). Recursively finds
  * the index of the last occurance of target in items[0...cur]
  */
private static int findLastOccurance(Object[] items, Object target, int cur){
    if(curr == -1) //We went past the start - missed it.
        return -1;
    else if (target.equals(items[cur])) //Found it
        return cur;
    else
        return lineSearchLast(items, target, curr-1); //Work backwards
}

Upvotes: 1

Related Questions