黑马程序员技术交流社区

标题: 数组折半查找 [打印本页]

---

作者: 复仇的撒旦    时间: 2015-3-2 11:23
标题: 数组折半查找
给定一个数字，插入一个有序的数组中，要求数组仍然有序
public static int getIndex_2(int[] arr,int key)
        {
                int min = 0,max = arr.length-1,mid;

                while(min<=max)
                {
                        mid = (max+min)>>1;

                        if(key>arr[mid])
                                min = mid + 1;
                        else if(key<arr[mid])
                                max = mid - 1;
                        else
                                return mid;
                }
                return min;
求解答，最后一句为什么是返回min  我觉得返回mid?

---

作者: shuren2015    时间: 2015-3-2 11:57
因为这样会出现问题，有时候应该返回mid,但有时候又应该返回mid+1,多想想，你总会明白的

---

作者: zfgrinm    时间: 2015-3-2 12:33
最后一个return min是在数组中不存在这个数key，且min>max时才读到的，此时的min刚好比max大1，那么此时的mid=(max+min)>>1=max,而我们要找的是插入位置，此插入位置应该在mid的后一位，当然就是min了

---

作者: wdhm5423    时间: 2015-3-2 12:51


当程序跳出循环，说明key的大小不在数组的最小和最大范围内。
分两种情况：
当key比数组最小还小，那么循环内始终都是max=mid-1，min=0，直到max=min-1=-1；要返回也是返回max，-1表示要插入到开头。
当key比数组最大还大，那么循环内始终都是min=mid+1，max=arr.length-1，直到min=max+1=arr.length；要返回也是返回min，arr.length表示要插入到结尾。所以可以在进入循环之前加入：
if(key<arr[0])  return -1;
if(key>arr[arr.length-1]) return arr.length;
或在循环之后加入：
if(key<arr[0])  return max;
if(key>arr[arr.length-1]) return min;

---

作者: yangruijing    时间: 2015-3-2 12:57
因为当key的值大于arr[mid]时，min=mid+1；这样查找下来，最终key应插入的位置是min

---

作者: 复仇的撒旦    时间: 2015-3-2 13:12

wdhm5423 发表于 2015-3-2 12:51
当程序跳出循环，说明key的大小不在数组的最小和最大范围内。
分两种情况：
当key比数组最小还小，那么循环 ...

很详细呀~！

---

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

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