我实际上需要通过仅使用被参数化的构造函数中的搜索项来解决该问题。我该怎么做?我被程序卡住了!

我可以用Middle元素做得很好,但是当我尝试使用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;
}


它与中间元素配合得很好,但与其他元素结合在一起,没有解决方案。

最佳答案

您需要将更新的lu作为参数传递给递归方法。您正在做的是在每个调用中为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
}


注意事项:


基本条件(l <= u)。这将使我们能够检测到缺少的元素条件并终止递归。
每个递归调用中的return关键字,否则,您将始终返回-1。


更新:

如果已将lu声明为静态,则需要在进行递归调用之前对其进行更新。

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 = 0u = n - 1

10-07 19:26
查看更多