黑马程序员技术交流社区

标题: 关于二分查找，binarysearch [打印本页]

---

作者: 陈志强    时间: 2013-3-18 12:37
标题: 关于二分查找，binarysearch
在Collections这个工具类里面有binarySearch这个方法，功能是使用二分搜索法搜索指定列表，以获得指定对象。返回的值是插入点减一，这是为什么？
同时在毕老师的视频里为了理解这个插入点写了这个方法，也是二分查找，但是毕老师说的这个插入点也就是min所对应的元素，这个如何理解？
public static int halfSreach(List<String>list,String key)
{
        int max,min,mid;
        max=list.size()-1;
        min=0;

        while(min<=max)
        {
                mid=(max+min)>>1;
                String str=list.get(mid);
                int num=str.compareTo(key);
                if(num>0)
                        max=mid-1;
                else if(num<0)
                        min=mid+1;
                else
                        return mid;

        }
        return -min-1;//min就是插入点，这个如何理解呢？
}

---

作者: 郭利超    时间: 2013-3-18 12:56
在Collections这个工具类里面有binarySearch这个方法，功能是使用二分搜索法搜索指定列表，以获得指定对象。返回的值是插入点减一，这是为什么？
对象插入后 角标增加了一个  比如 元素插入到角标为8的位置 但是原先角标为8的位置上面还有元素 所以 返回的值是插入点减一
毕老师讲的Min 是整个元素的中间位置 就算你插入了一个元素  里面的元素增加了 Min代表的角标位置也随之变化了 所以 你懂的!

---

作者: 李尧    时间: 2013-3-18 16:36
我不知道该怎么表达了....你仔细看了老毕的视频,仔细推敲了这个算法的过程,应该不难理解.

---

作者: michaelchen    时间: 2013-3-18 17:35


给你举个例子吧，

int[] arr={1，2，3，5，6}
想通过二分法把4插入到这个数组中
1.        mid=(min+max)/2=2   arr[mid]=3 4>3 min=mid+1=3 max=4  min<max
2.        mid=(min+max)/2=3   arr[mid]=5 5>3 max=2  min=3 min>max  条件不满足，退出循环，而3正好是要插入到数组中的位置,所以插入的位置是min

---

作者: 陈志强    时间: 2013-3-18 23:52
标题: RE: 关于二分查找，binarysearch

michaelchen 发表于 2013-3-18 17:35
给你举个例子吧，

int[] arr={1，2，3，5，6}

int[] arr={1，2，3，5，6}
想通过二分法把4插入到这个数组中
1. mid=(min+max)/2=2 arr[mid]=3 4>3 min=mid+1=3 max=4 min<max
2. mid=(min+max)/2=3 arr[mid]=5 5>3 max=2 min=3 min>max

你这个有点绕，不知道该怎么看啊，你能不能转换一下或者标注下，谢谢啊

---

作者: michaelchen    时间: 2013-3-19 15:21


第一次:min=0  max=4 mid=(0+4)/2=2 arr[2]=3
要插入的数字4大于3,所以min=mid+1=3
这时候min<max,循环继续

第二次,min=3 max=4 mid=(3+4)/2=3 arr[3]=5
要插入的数字4小于5,所以max=mid-1=2
这时min>max,循环跳出,而这个时候min=3,刚好是4
要插入到数组中的位置,所以要插入的位置就是min

---

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

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