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

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
}

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

Linear Search Recursive Last Occurrence

java

recursion

data-structures

recursive-datastructures

linear-search