Java - 使二进制搜索递归

Question

所以几个星期以来我一直在来回尝试将以下代码创建为递归方法......

public static int binarySearch(Comparable[] objArray,Comparable item)
{       
    int lower=0;
    int upper=objArray.length -1;
    int i=-1;    // if -1 is returned the search failed;
    int compareResult;
    boolean found= false;
    while ((lower<=upper)&& (!found))
       {
        i=(lower+upper)/2;
        compareResult=item.compareTo( objArray[i]);
        if (compareResult<0)
           {
            upper=i-1;
           }
         else
            if (compareResult>0)
               {
                lower=i+1;
               }
         else
            {
                found=true;    //item found in spot i
            }

       }// end of while
       if (found==false) return -1; else return i;

}

我知道我必须重新定义整数并使用几个ifs,但没有while循环我不明白如何获得我想要的最终递归代码.有什么建议？谢谢

-D

Answer 1

阻止你看到递归的主要问题是你的方法的参数只是一个数组和一个比较器.如果你传递起始和结束索引(通常在旧语言中做了什么),你会看到递归的可能性.

我通常不喜欢为这些问题提供伪代码,而是更愿意给出关于算法结构和性质的提示.但是,当您以这种方式定义方法时,您无法将2 + 2放在一起.所以我将在这里做一个例外:

而不是这(你有什么):

public static int binarySearch(Comparable[] objArray,Comparable item)
{       
    int lower=0;
    int upper=objArray.length -1;

你有这个(这是类似java的伪代码,高度简化,没有错误检查,你需要处理实际的语法细节):

public static int binarySearch(Comparable[] objArray,Comparable item)
{       
    return bSearch(objArray, item, 0, objArray.length -1);
    ....

private static int bSearch(Comparable[] objArray,Comparable item, int lower, int upper)
{
   if( lower > upper /* not found */){ return -1; };

   int pivot = ((int)((upper - lower) / 2)) + lower;

   int cmp = objArray[pivot].compareTo(item);

   if( cmp == 0 ){ return pivot; }
   else if (cmp < 0 ){ return bSearch(objArray,item, lower, pivot - 1); }
   else{ return bSearch(objArray,item, pivot+1, upper); }
}

同样,您需要处理实际的语法和参数验证,但除此之外,这是递归二进制搜索的典型伪代码.你应该已经看过这个,并且最近在二年级的编程课程中也会恶心.

递归发生在:

1. 如果您的数组已排序,并且

2. 如果你在中间开始比较,又称枢轴,

3. 比较失败了,

4. 然后

5. 你知道你只需搜索一半(如果目标>枢轴则是上半部分,如果是目标<枢轴则是下半部分).

所以你拿下你要搜索的一半,然后再次执行相同的步骤.有什么更好的方法可以调用完全相同的算法,只是那个部分的完全相同的函数,输入的子集？

这是递归.

编辑:在前面的例子中详细说明,当你想要/需要在Java中递归地实现某些东西时,最好有一个实用的方法,将数据结构作为一个整体(比如你在数组中所做的那样的数组和比较对象)例).

然后让该调用,它的实际递归的内部方法(并具有处理参数的传递.)这样做的原因是,来电者不必通过上,下指标(因为他们可以计算出来的数组对象.)

在其他的,低级语言如C,Pascal和Ada的,你有时不能计算这样的论点,并与您的来电者明确传递的参数来声明递归函数.

为什么我bSearch在上面的伪代码中将递归拆分为一个单独的函数.