黑马程序员技术交流社区

标题: 小白又遇新问题！关于用折半的方法插入有序数组的问题~ [打印本页]

作者: 立志转行 时间: 2015-5-7 22:32
标题: 小白又遇新问题！关于用折半的方法插入有序数组的问题~
class getIndex
{
public static void main(String[] args)
{
int[] arr = {1,3,5,7,9};
int index1 = getIndex(arr,2);
System.out.println("2应该放在数组中角标为"+index1+"的位置");
int index2 = getIndex(arr,8);
System.out.println("8应该放在数组中角标为"+index2+"的位置");
int index3 = getIndex(arr,7);
System.out.println("5应该放在数组中角标为"+index3+"的位置");
}
public static int getIndex(int[] arr,int key)
{
int min = 0,max = arr.length-1,mid;
while (min <= max)
{
mid = (min +max)>>1;
if (key <arr[mid])
{
max = mid -1;
}
else if (key > arr[mid])
{
min = mid + 1;
}
else
return mid;
}
return min;//毕老师在这儿用的返回值是min；
}
}
分析为什么会是min：
1、如果插入的是2，第1轮循环mid = 2,2<arr[2],然后max=1，min=0,mid = 0；
2、第2轮循环mid = 0,2>arr[0],然后min=max=1,mid=1;
3、第3轮循环mid=1，2<arr[1],然后max=0，min=1，min>max,结束循环，结束时min=1；
--------------------------------------------------------------------------
1、如果插入的是8，第1轮循环mid=2,8>arr[2],然后min=3，max=4，mid=3；
2、第2轮循环mid=3,8>arr[3],然后min=4,max=4,mid=4;
3、第3轮循环mid=4.8<arr[4],然后min=4，max=3，min>max,结束循环，结束时min=4
----------------------------------------------------------------------------
1、如果插入的是5，第1轮循环mid=2,5==arr[2],mid=2.return mid=2结束

但是经过分析，我觉得结束时min==mid，那么红字部分改为return mid理论上ok;
但是报错，可能尚未初始化变量mid？？为什么会这么报错呢？大神请指教~

作者: 立志转行 时间: 2015-5-7 23:12
来人啊~

作者: 立志转行 时间: 2015-5-8 07:07
大神们给看看吧

作者: 396460221 时间: 2015-5-8 10:51
局部变量没有初始化不能使用，成员变量可以不用初始化，因为有默认值。返回min是指你想插入的数在数组中要插入的位置，返回mid是指你查找到的数在数组中的位置。

作者: 立志转行 时间: 2015-5-8 11:38

396460221 发表于 2015-5-8 10:51
局部变量没有初始化不能使用，成员变量可以不用初始化，因为有默认值。返回min是指你想插入的数在数组中要 ...

1、我见视频上说for定义的局部变量结束后会释放，在外面不可以用；但while定义的局部变量结束后不会释放在外面可以使用啊？我理解错了？
2、既然需要定义那就在外面也定义个mid = 0；然后return mid；是不是也可以达到同样的效果？
请指教

作者: lovejjfg 时间: 2015-5-8 11:41
你的min没有初始化，当然会给你报错咯，另外我觉得while条件可以不要=条件，min<max;返回-min-1,这样才能提示出超找的元素不存在。具体的你可以看看毕老师数组那里的视频还有后面17天的binary查找的视频。

作者: 396460221 时间: 2015-5-8 15:52

立志转行发表于 2015-5-8 11:38
1、我见视频上说for定义的局部变量结束后会释放，在外面不可以用；但while定义的局部变量结束后不会释放 ...

变量作用发域不用，for内定义的只能在for内用，while有条件要判断，一般会在while之前定义该局部变量，这个局部变量的作用域会比这个while的范围要大。

循环的结束因为min>max，即此时的两个角标是相邻的，而mid = (min+max)/2,因为是整型的，所以会取整数，取min和max中较小的那个就是max,即mid=max,所以返回mid的位置是不正确的。

作者: 立志转行 时间: 2015-5-8 16:42

lovejjfg 发表于 2015-5-8 11:41
你的min没有初始化，当然会给你报错咯，另外我觉得while条件可以不要=条件，min ...

我就是看的毕老师的视频，看到数组这儿有不理解的地方。。。
1、必须要=，否则key=3，无法插入{4}中；
2、不能返回min-1啊，key=2,插入{1，3,4}时它会插到1前面。

作者: 立志转行 时间: 2015-5-8 16:51

396460221 发表于 2015-5-8 15:52
变量作用发域不用，for内定义的只能在for内用，while有条件要判断，一般会在while之前定义该局部变量，这 ...

根据我的理解，当min>max时，循环会直接跳出，不会再去执行mid = (min+max)/2了，所以mid还保留在上一次循环时mix<max，所以mid取小等于min，return mid；运行后也达到了同样的效果，不知道是不是没有碰到特殊情况？

作者: 396460221 时间: 2015-5-9 08:57

立志转行发表于 2015-5-8 16:51
根据我的理解，当min>max时，循环会直接跳出，不会再去执行mid = (min+max)/2了，所以mid还保留在上一次 ...

看了你的分析，你的应该是对的。

作者: 立志转行 时间: 2015-5-9 10:35

396460221 发表于 2015-5-9 08:57
看了你的分析，你的应该是对的。

看见你也回答那3道题了！我就在你楼上哈哈~

作者: 立志转行 时间: 2015-5-30 10:37
本帖最后由立志转行于 2015-5-30 10:39 编辑

396460221 发表于 2015-5-9 08:57
看了你的分析，你的应该是对的。

哈哈，我知道原因了，在 return mid时，它会再去把最新的min和max代入，重新执行一遍mid = (min+max)>>1,所以还是会执行的，你说的是对的！[1,2,3,4,6,7]中查找5就会发现结果不一样

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2