java - 如果所查找的值不存在，递归二分查找何时终止

Question

我正在使用二分搜索，我知道如何以非递归方式编写此方法，但我的教授决定使用递归来编写它，这是他的代码:

public static boolean Bsearch(int A[],int low,int high,int key){
     if(low>high)
          return false;
     int mid=(low+high)/2;

     if(A[mid]==key)
       return true;
     if(A[mid]<key)
       return Bsearch( A, mid+1, A.length, key);
     if(A[mid]>key)
       return Bsearch(A, 0, mid-1, key);

    return false;
}

我的问题是它如何返回 false 以及何时停止再次调用该方法并返回 false 实际上我不明白它将如何返回 false。我们总是有 A[mid] 大于或小于或等于我正在搜索的键值。

Answer 1

这部分将是您的中止条件:

 if(low>high)
      return false;

最后 - 如果没有找到元素 - 将调用递归，并且 low beeing 大于 high - 并且立即中止。

看看这两个调用:

if(A[mid]<key)
   return Bsearch( A, mid+1, A.length, key);
if(A[mid]>key)
   return Bsearch(A, 0, mid-1, key);

如果 mid+1 大于 A.length，调用将返回 false。

如果 mid-1 小于 0，调用将返回 false。

如果您将列表缩减为一个元素，则这两种情况都会出现 - 则 mid+1和mid-1始终匹配 low > high情况。

最终的“return false”语句永远不会被命中 - 它只需要存在，因为编译器无法知道其中一个 IF 语句始终为 true。可以通过使用 if、else if、else 来避免:

if(A[mid]==key)
  return true;
else if(A[mid]<key)
  return Bsearch( A, mid+1, A.length, key)
else 
  //this is an implict A[mid]>key
  return Bsearch(A, 0, mid-1, key)

 //return false; //no longer required.

---

编辑:抱歉，没有注意到:当您进入下一个递归步骤时，您不应该以“0”开始或运行直到“A.length” - 相反，您应该保持在“low”或运行直到“高” - 否则你会上下运行数组，上下，上下......

像这样修改递归方法调用，那就应该没问题了:

 if(A[mid]==key)
       return true;
 if(A[mid]<key)
       return Bsearch( A, mid+1, high, key);
 if(A[mid]>key)
       return Bsearch(A, low, mid-1, key);

对于indexOutOfBound 异常，请使用 boolean f= Bsearch(A, 0, A.length -1, 9); 调用第一个方法(注意-1)