黑马程序员技术交流社区

标题: 毕老师折半查找中一个例题 [打印本页]

---

作者: jiahuiting    时间: 2013-9-24 13:09
标题: 毕老师折半查找中一个例题


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


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

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值就是他所要的位置呢

---

作者: 369833818    时间: 2013-9-24 13:26
方法需要返回值，return min,min=0，是指没有找到元素

---

作者: jiahuiting    时间: 2013-9-24 13:31

369833818 发表于 2013-9-24 13:26
方法需要返回值，return min,min=0，是指没有找到元素

这个视频中说，min返回值就是元素要插入的位置，当这个元素不在数组中就会出现这种情况，我敲代码试了下对着呢，可是我不是很清楚为什么。

---

作者: 369833818    时间: 2013-9-24 13:38

jiahuiting 发表于 2013-9-24 13:31
这个视频中说，min返回值就是元素要插入的位置，当这个元素不在数组中就会出现这种情况，我敲代码试了下 ...

把数据代入方法运行一次应该就可以弄清楚了，或者你把主函数代码贴出来看看

---

作者: 落木萧萧    时间: 2013-9-24 13:39


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

---

作者: 梁贺    时间: 2013-9-24 13:51
结果是这样的 比如 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就是你要找的那个数如果存在该在的位置，也就是插入数据该插入的地方。希望你懂了~

---

作者: 陈洋    时间: 2013-9-24 15:13
基本思想：
将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

---

作者: 黄炳期    时间: 2013-9-24 15:42
如果问题得到解答，麻烦及时修改主题为“已解决”。

---

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

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