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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© t_mac 黑马帝   /  2011-12-12 10:04  /  2162 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 t_mac 于 2011-12-12 15:23 编辑

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啊?

评分

参与人数 1技术分 +1 收起 理由
吴上储 + 1

查看全部评分

4 个回复

倒序浏览
wsssx 2011-12-12 11:45:17
沙发
提示: 作者被禁止或删除 内容自动屏蔽
回复 使用道具 举报
李明 黑马帝 2011-12-12 14:48:52
藤椅
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:44
板凳
李明 发表于 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:29
报纸
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代替结果是一样的。
        }

评分

参与人数 1技术分 +1 收起 理由
王德云 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马