常见的二分搜索，这个递归为什么老是陷入死循环？
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);
}
}
------解决方案--------------------
递归调用是不需要加循环的....因为递归本身就是一种循环了
另外,递归一定要用一个结果变量来接收每次调用的结果