黑马程序员技术交流社区

标题: 集合二分法查找的疑惑 [打印本页]

---

作者: t_mac    时间: 2011-12-12 10:04
标题: 集合二分法查找的疑惑


import java.util.*;
public class CollectionsDemo {
        public static void main(String[] args) {
                List<String> al = new ArrayList<String>();
                al.add("abc");
                al.add("z");
                al.add("qq");
                al.add("kkkkk");
                al.add("aaaa");
                Collections.sort(al);
                System.out.println(al);
                int index =halfSearch(al,"aaa");
                System.out.println(index);
        }
        public static int halfSearch(List<String> list,String s){
                int min = 0,max = list.size()-1;
                int mid = 0;
                while(min<max){
                        mid = (min+max)>>1;
                String str = list.get(mid);
                int num = str.compareTo(s);
                if(num<0)
                        min = mid+1;
                else if(num>0)
                        max = mid-1;
                else
                        return mid;
                }
                return -min-1;
        }
}

最后一个return返回的是-（插入点）-1  那这里的min就是插入点，为什么插入点是min啊？

---

作者: wsssx    时间: 2011-12-12 11:45
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: 李明    时间: 2011-12-12 14:48
public static int halfSearch(List<String> list,String s){
                int min = 0,max = list.size()-1;
                int mid = 0;
                while(min<max){
                        mid = (min+max)>>1;
                String str = list.get(mid);
                int num = str.compareTo(s);
                if(num<0)
                        min = mid+1;
                else if(num>0)
                        max = mid-1;
                else
                        return mid;
                }
                return -min-1;//这一句是在while循环不执行的时候才会执行，此时min就等于0，所以此处用0代替结果是一样的。
        }

---

作者: t_mac    时间: 2011-12-12 15:06

李明 发表于 2011-12-12 14:48
public static int halfSearch(List list,String s){
                int min = 0,max = list.size()-1;
...

我是想知道插入点是怎么算出来的，因为我对这个不理解

---

作者: 李明    时间: 2011-12-12 15:18

t_mac 发表于 2011-12-12 15:06
我是想知道插入点是怎么算出来的，因为我对这个不理解

public static int halfSearch(List<String> list,String s){
                int min = 0,max = list.size()-1;
                int mid = 0;
                while(min<max){
                        mid = (min+max)>>1;//mid取得中间值角标，>>1相当于/2.
                String str = list.get(mid);//取得中间值角标对应的字符串。
                int num = str.compareTo(s);//按自然字母顺序比较s和中间值，str大于s，则返回1，小于返回-1,等于返回零
                if(num<0)
                        min = mid+1;//str小于s，表示，插入位置比str大
                else if(num>0)
                        max = mid-1;//str大于s，表示，插入位置比str小
                else
                        return mid;//正好就是中间值位置
                }
                return -min-1;//这一句是在while循环不执行的时候才会执行，此时min就等于0，所以此处用0代替结果是一样的。
        }

---

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

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