黑马程序员技术交流社区
标题:
折半查找,程序编译通过不能执行,帮忙找错
[打印本页]
作者:
朱秀梅
时间:
2012-6-12 23:27
标题:
折半查找,程序编译通过不能执行,帮忙找错
这是我的代码
/*
折半查找
*/
class HalfSearch
{
public static void main(String[] args)
{
int arr[] = {1,3,5,6,7,9,12,24};
//System.out.println(halfSearch( arr, 0, arr.length, 2 ));
int num = halfSearch( arr, 23 );
System.out.println(num);
}
private static int halfSearch ( int arr[], int key )
{
int left, right, mid;
left = 0;
right = arr.length - 1;
while ( left < right )
{
mid = ( left + right ) / 2;
if ( key == arr[mid] )
{
return mid;
}
else if ( key < arr[mid] )
{
right = mid;
}
else if ( key > arr[mid] )
{
left = mid;
}
}
return -1;
}
}
编译通过但是达不到要求的结果
作者:
王晓新
时间:
2012-6-12 23:36
class HalfSearch
{
public static void main(String[] args) throws Exception
{
int arr[] = {1,3,5,6,7,9,12,24};
int num = halfSearch( arr, 23 );
System.out.println(num);
}
private static int halfSearch ( int arr[], int key )
{
int left, right, mid;
left = 0;
right = arr.length;
while ( left < right )
{
mid = ( left + right ) / 2;
if ( key == arr[mid] )
{
return mid;
}
else if ( key < arr[mid] )
{
right = mid-1;
}
else if ( key > arr[mid] )
{
left = mid+1;
}
}
return -1;
}
}
复制代码
我运行成功了。。你看看
作者:
江南
时间:
2012-6-12 23:36
你的折半查找的函数中的条件语句有错,修改之后如下:
class HalfSearch
{
public static void main(String[] args)
{
int arr[] = {1,3,5,6,7,9,12,24};
//System.out.println(halfSearch( arr, 0, arr.length, 2
));
int num = halfSearch(arr,23);
System.out.println(num);
}
private static int halfSearch (int arr[],int key)
{
int left, right, mid;
left = 0;
right = arr.length - 1;
while ( left < right )
{
mid = ( left + right )/ 2;
if ( key == arr[mid] )
{
return mid;
}
else if ( key < arr[mid] )
{
right = mid-1;
}
else if ( key > arr[mid] )
{
left = mid+1;
}
}
return -1;
}
}
作者:
王晓新
时间:
2012-6-12 23:38
{:soso_e100:}毕向东老师java基础视频中专门对折半查找做了讲解,你可以去看看
作者:
王超
时间:
2012-6-12 23:52
正确的是:
else if ( key < arr[mid] )
{
right = mid-1; //当你要查找的数字小于第一次查找的中间值的时候,右边的范围下标就移动到中间值减1的位置,因为不包含中间值
}
else if ( key > arr[mid] )
{
left = mid+1;////当你要查找的数字大于第一次查找的中间值的时候,左边的范围下标就移动到中间值加1的位置}
作者:
葛奎
时间:
2012-6-13 00:09
class Test15
{
public static void main(String[] args)
{
int arr[] = {1,3,5,6,7,9,12,24};
//System.out.println(halfSearch( arr, 0, arr.length, 2 ));
int num = halfSearch(arr,24);
System.out.println(num);
}
private static int halfSearch ( int arr[], int key )
{
int left, right, mid;
left = 0;
right = arr.length - 1;
while ( left <=right )
{
mid = ( left + right ) / 2;
if ( key == arr[mid] )
{
return mid;
}
else if ( key < arr[mid] )
{
right = mid-1;
}
else if ( key > arr[mid] )
{
left = mid+1;
}
}
return -1;
}
}
//改成这样就行了
作者:
胡大强
时间:
2012-6-13 00:16
private static int halfSearch ( int arr[], int key )
{
int left, right, mid;
left = 0;
right = arr.length - 1;
while ( left < right )
{
mid = ( left + right ) / 2;
if ( key == arr[mid] )
{
return mid;
}
else if ( key < arr[mid] )
{
right = mid-1;
}
else if ( key > arr[mid] )
{
left = mid+1;
}
}
return -1;
}
}
}
很明显,当key<arr[mid],说明key在arr【mid】的左边,所以缩小范围后,最右边的right=mid-1,而不是等于mid.
kry>arr[mid]时,原理相同!
作者:
李元峰
时间:
2012-6-13 11:27
我运行你的代码 发现 你的程序 在 left=6, right=7 也就是 在12 和 24 这两个数之间不停的循环 ,程序进入了死循环
你发现没有 这时候你的CPU是消耗很大的,因为程序进入了死循环不停的在 12 和24 之间做比较
为什么呢?我给你分析一下
第一次
left=0 right=7 mid=3, 对应的分别是 1,24,6, arr[mid]=6 显然23>arr[mid]
第二次
left=3, right=7, mid=5,对应的分别是 6,24,9, arr[mid]=9 显然 23>arr[mid]
第三次
left=5,right=7,mid=6, 对应的分别是9,24,12, arr[mid]=12 ,显然23>arr[mid]
第四次
left=6,right=7,mid=6,对应的分别是12,24,12 arr[mid]=12 ,显然23>arr[mid]
第五次
left=6,right=7,mid=6,对应的分别是12,24,12 arr[mid]=12 ,显然23>arr[mid]
。。。
。。。
。。。
所以循环一直 在这里循环
所有没有结果 永远这样循环下去,知道天荒地老!
解决的办法是 你应该这样写
right=mid-1
left=mid+1
因为当你判断 (key<arr[mid]) 或者 (key>arr[mid]) 时
arr[mid] 这个数已经比较过了,所有索引 right, left就必须 移动 要么减一 要么加一
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2