A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© jiahuiting 中级黑马   /  2013-9-24 13:09  /  2184 人查看  /  7 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 jiahuiting 于 2013-9-24 14:26 编辑

毕老师在折半查找的讲解中,有个例题是


/**
需求:想要将一个元素插入到一个有序数组中,还要保证插入后该数组有序
*/

public static int halfSearch(int[] arr,key)
{
        int min=0;
        int max=arr.length-1;
        while(min<max)
                {
                int mid=(min+max)>>1;
                if(arr[mid]>key)
                        min=mid+1;
                else if(arr[mid]<key)
                        max=mid-1;
                else
                        return mid;}
                return min}


目的是返回该元素应该插入的位置。
我不懂为什么最后都不满足的时候,返回的min值就是他所要的位置呢

评分

参与人数 1技术分 +1 收起 理由
乔兵 + 1

查看全部评分

7 个回复

倒序浏览
方法需要返回值,return min,min=0,是指没有找到元素
回复 使用道具 举报
369833818 发表于 2013-9-24 13:26
方法需要返回值,return min,min=0,是指没有找到元素

这个视频中说,min返回值就是元素要插入的位置,当这个元素不在数组中就会出现这种情况,我敲代码试了下对着呢,可是我不是很清楚为什么。
回复 使用道具 举报
jiahuiting 发表于 2013-9-24 13:31
这个视频中说,min返回值就是元素要插入的位置,当这个元素不在数组中就会出现这种情况,我敲代码试了下 ...

把数据代入方法运行一次应该就可以弄清楚了,或者你把主函数代码贴出来看看
回复 使用道具 举报
本帖最后由 落木萧萧 于 2013-9-24 13:40 编辑

并不是都不满足的时候才返回min,首先halfSearch这个方法需要一个返回值,而上一条语句return mid包含在while语句块中,在极端情况下,例如arr里面什么都没有,那么while语句就不能执行,那就只有return min,又因为min的值是0,刚好是数组的第一个位置。
PS.说得有点乱。
PPS.代码最后还是放到代码块里。

评分

参与人数 1技术分 +1 收起 理由
黄炳期 + 1 赞一个!

查看全部评分

回复 使用道具 举报
结果是这样的 比如 1 3  4 6 7 8几个数,它要折半查找5 ,则key的值为5.
min =0; max = 5; mid =2;
即arr[mid]=4,而key =5>4,所以min=mid+1=3 ,max =5,mid =4;
arr[mid]=7>key
min =3,max = mid-1=3;mid =3;
arr[mid] = 6>key
min =3 max = mid-1=2; min>max 没有找到跳出循环
重点是此时左右两边折半,在没有找到的情况下跳出循环的那个最小值min就是你要找的那个数如果存在该在的位置,也就是插入数据该插入的地方。希望你懂了~

评分

参与人数 1技术分 +1 收起 理由
黄炳期 + 1 很给力!

查看全部评分

回复 使用道具 举报
陈洋 中级黑马 2013-9-24 15:13:56
7#
基本思想:
将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。

评分

参与人数 1技术分 +1 收起 理由
黄炳期 + 1 赞一个!

查看全部评分

回复 使用道具 举报
如果问题得到解答,麻烦及时修改主题为“已解决”。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马