java - 使用递归的二分搜索仅采用参数中的搜索值

Question

我实际上需要通过仅在参数化构造函数中获取搜索项来解决问题。我该怎么做？我被这个程序困住了!

我可以很好地使用中间元素，但是当我尝试使用 mid 以外的其他元素时，它显示堆栈溢出错误。

public static int binary_search(int v)
{
    l=0;
    u=n-1;
    int mid = (l+u)/2;
    if(A[mid]==v)
        return 1;
    else if(v<A[mid])
    {
        binary_search(v);
        mid = mid-1;
    }
    else if(v>A[mid])
    {
        binary_search(v);
        mid = mid+1;
    }
    return -1;
}

对于中间元素来说效果很好，但对于其他元素来说，没有解决方案。

Answer 1

您需要传递更新后的l和u作为递归方法的参数。您正在做的是将相同的值分配给 l (=0) 和 u (=n-1) 在每次调用中。换句话说，每次递归调用都不能解决更小的问题。这是相同的问题，因此会导致 StackOverflow。

这是一个伪代码

int binarySearch(int v, int l, int u) {
    if (l <= u) {
       find mid
       is the element at mid:
           return 1;// Can be 'mid' to return the index at which it was found.
       should we go left:
           return binarySearch(v, l, mid - 1);
       should we go right:
           return binarySearch(v, mid + 1, u);
    } 
    return -1; //Not found
}

注意事项:

1. 基本条件 ( l <= u )。这将使我们能够检测缺失元素的情况并终止递归。
2. return每次递归调用中的关键字，如果没有该关键字，您将始终返回 -1。

更新:

如果您有l和u声明为静态，您需要在递归调用之前更新它们。

int binarySearch(int v) {
    if (l <= u) {
       find mid
       is the element at mid:
           return 1;// Can be 'mid' to return the index at which it was found.
       should we go left:
           u = mid - 1
           return binarySearch(v);
       should we go right: 
           l = mid + 1
           return binarySearch(v);
    } 
    return -1; //Not found
}

注意:您必须设置l = 0和u = n - 1在调用此方法之前。