java - 在 Java 中使用递归进行二值搜索

Question

我正在学习递归，因此尝试通过实现 BinarySearch 算法来练习它。

public class BinarySearch {
    public int search(int[] items, int searchTerm, int startIndex, int endIndex) {
        int midIndex = (startIndex + endIndex)/2 ;
        System.out.println("Midpoint: "+midIndex);
        if(searchTerm == items[midIndex]) {
            return midIndex;
        } else if(searchTerm > items[midIndex]) {
            search(items, searchTerm, midIndex, endIndex);
        } else if(searchTerm < items[midIndex]) {
            search(items, searchTerm, startIndex, midIndex);
        } else {
            return -1;
        }
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int[] items = { 1, 7, 9, 11, 22, 55, 67 };
        int index = bs.search(items, 7, 0, items.length-1);
        System.out.println(index);
    }

}

search 是使用项目数组、我想要搜索的值以及项目可能存在的数组的开始和结束索引递归调用的方法。

首先，我获取中点，如果中点处的项目与 searchTerm 匹配，则返回它。如果 searchTerm 大于中点处的值，则我再次调用搜索方法，其中中点为 startIndex，数组中的最后一项为 endIndex。

类似地，如果 searchTerm 小于中点处的值，则将 startIndex 和中点作为搜索的开始值和结束值传递。

比方说，我想搜索 7。在第一次迭代中，3 将是中点，因此索引 3 处的值将是 11。由于 7 < 11，将再次调用搜索，startIndex 为 0，endIndex 为3. 现在，中点将为 7，因此应返回索引 7(即 1)。但是，返回的值是-1，这是不正确的。

当我尝试使用 Eclipse 调试器对其进行故障排除时，我发现即使在

中找到匹配项之后

if(searchTerm == items[midIndex]) {
            return midIndex;
}

执行以下代码，而不是退出该方法

else if(searchTerm < items[midIndex]) {
            search(items, searchTerm, startIndex, midIndex);
        }

然后返回-1。我觉得这可能与递归有关，因为由于代码的递归性质，之前对 search() 的调用仍然在堆栈中，并且它可能会从堆栈中弹出。然而，我实在无法理解。使用递归实现 BinarySearch 的正确方法是什么？

Answer 1

public int search(int[] items, int searchTerm, int startIndex, int endIndex)
{
  int midIndex = (startIndex + endIndex) / 2; 
  if (startIndex > endIndex)
    return -1;
  else if (searchTerm == items[midIndex]) 
    return midIndex;
  else if (searchTerm < items[midIndex]) 
    return search(items, searchTerm, startIndex, midIndex - 1);
  else // (searchTerm > items[midIndex]) 
    return search(items, searchTerm, midIndex + 1, endIndex);
}

在此版本的二分搜索中，我使用了 midIndex ± 1:我这样做是因为在您的 if 语句中您已经检查了 items[midIndex] 是否相等到 searchTerm，这就是为什么在接下来的调用中没有必要考虑 items[midIndex]。