时间戳

首页 > 解决方案 > 递归线性搜索算法

java - 递归线性搜索算法

问题描述

我有一个家庭作业，要创建一个从一个索引到另一个索引的递归线性搜索算法。出于某种原因，以下代码每次都返回 -1。

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


}

这就是我所说的：

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

标签： javalistrecursion

解决方案

索引不是列表中的元素，因此pList.indexOf(pBeginIdx)总是会返回-1。此外，indexOf恕我直言，您应该自己实现搜索。您已经正确检查了元素是否等于键 - 您只需要返回它：

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

推荐阅读