日期:2014-05-20  浏览次数:20673 次

请帮忙梳理一下这个方法
常见的二分搜索,这个递归为什么老是陷入死循环?
public   class   BinarySearch2
{
public   static   int   binarySearch(int   a[],int   x,int   m,int   n)
{
int   left=m;
int   right=n-1;
while(left <=right)
{
int   middle=(left+right)/2;
if(x==a[middle])   return   middle;
if(x> a[middle])   binarySearch(a,x,middle+1,right);
else   binarySearch(a,x,left,middle+1);
}
return   -1;
}
public   static   void   main(String[]   args)
{
int   a[]={1,12,23,34,55,76,87,98,99,101,120};
int   b=binarySearch(a,1,0,5);
int   c=binarySearch(a,98,0,a.length);
//int   d=binarySearch(a,100,0,a.length);
System.out.println(b);
System.out.println(c);
//System.out.println(d);
}
}

------解决方案--------------------
讨厌算法,不看……
------解决方案--------------------
public class BinarySearch2
{
public int binarySearch(int a[],int x,int left,int right)
{

int result;

int middle=(left+right)/2-1+(left+right)%2;
if(left==right) middle=left;
System.out.println( "middle: "+middle+ " left: "+left+ " right: "+right+ " num: "+a[middle]);
if(x==a[middle])
{
System.out.println( "zhao dao le ");
return middle;

}
else
{
if(x> a[middle])
{
System.out.println( "zai you bian ");
result=binarySearch(a,x,middle+1,right);
}
else
{
System.out.println( "zai zuo bian ");
result=binarySearch(a,x,left,middle-1);
}

}
if(left> right)result =-1;
return result;
}
public static void main(String[] args)
{
int a[]={1,12,23,34,55,76,87,98,99,101,120};
//int b=binarySearch(a,1,0,5);

int c=new BinarySearch2().binarySearch(a,98,0,a.length);
//int d=binarySearch(a,100,0,a.length);
//System.out.println(b);
System.out.println(c);
//System.out.println(d);
}
}
------解决方案--------------------
递归调用是不需要加循环的....因为递归本身就是一种循环了

另外,递归一定要用一个结果变量来接收每次调用的结果