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

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

我的问题是它会怎样 return false 什么时候会停止再次调用该方法 return false 其实我不明白它会怎样 return false。我们总是有 A[mid] 大于或小于或等于我正在搜索的键值。

Answer 1

你是对的，如果数组中不存在键，这将永远不会终止。应该有一个基本案例来检查何时发生这种情况？

由于这是学校的问题，所以我只给出一些重点问题。

这会发生在什么时候？如果您一直搜索到密钥可能存在的最后一个可能位置，那么什么时候会发生？让程序员知道键不存在于数组中的参数是什么？

提示：寻找的关键是高低之间的关系。

public boolean Bsearch(int A[],int low,int high,int key){
 //Should have a if statement check here to see if the condition is hit alerting that the array doesn't contain the key
 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;
}

Answer 2

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

 if(low>high)
      return false;

最后 - 如果没有找到任何元素 - 将调用递归，低蜂鸣大于高蜂鸣 - 并立即中止。

看看这两个调用：

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，调用将 return 为假。

如果 mid-1 小于 0，调用将 return 为假。

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

最终的 "return false" 语句将永远不会被命中 - 它只需要在那里，因为编译器无法知道其中一个 IF 语句总是为真。可以通过使用 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" 或运行直到 "high" - 否则你运行将数组上下，上下，上下......

像这样修改递归方法调用，应该没问题：

 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）

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

When does recursive binary search terminate if the sought value is absent

java

binary-search