java - 线性搜索递归最后一次出现

Question

我正在尝试对找到最后一次出现的目标的数组执行线性搜索。我被卡住了，因为我的搜索只找到目标的第一次出现而不是最后一次出现。

/** 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);

Answer 1

您不应该需要两个索引参数 - 一个（当前索引）应该可以解决问题。此外，为了确保您首先找到最后一个等效元素，谨慎的做法是从后面开始并向前推进。

/** 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
}