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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 突然世界晴 中级黑马   /  2015-3-11 22:38  /  1059 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

  1. public static int halfSearch(List<String> list,String key)
  2.         {
  3.                 int max,min,mid;
  4.                 max = list.size()-1;
  5.                 min = 0;

  6.                 while(min<=max)
  7.                 {
  8.                         mid = (max+min)>>1;//  /2;

  9.                         String str = list.get(mid);

  10.                         int num = str.compareTo(key);
  11.                         if(num>0)
  12.                                 max = mid -1;     //为什么max=min-1????????????????
  13.           else if(num<0)
  14.                                 min = mid + 1; //为什么max=min+1????????????????
  15.           else
  16.                                 return mid;
  17.                 }
  18.                 return -min-1;  //为什么返回  -min-1????????????????
  19.         }
复制代码

2 个回复

倒序浏览
首先你要明确compareTo方法是将两个字符串进行每个字符的Ascii码比较,发现不同时返回str相对位置减去key相对位置的字符的值,照你的题目,两个字符串的第一处不同出现在第一位,str的ascii码为a,key的ascii码为b所以,返回num=a-b.如果num>0;证明key的值大于了str,证明中间值出现在初始中间值的左边需要在初始中间值的左边-一位开始继续查找比如1-100之间你初始中间值为50当你要找的值<50的时候你需要在1-49之间找这时候min的值就是1不变,而最大值max成了max=50-1;反之大于了50你就需要改变最小值min=50+1;需要在51-100之间去寻找。至于为什么返回-min-1;在我看来这时候min>max返回的不过就是一个负数罢了、证明需要找的数不在这个这之间。也可以选择直接返回-1;希望能帮到你!
回复 使用道具 举报
compareTo方法的返回值有正数、负数和零。当num不为零时,就说明字符串str与字符串key不相同,也就是mid位置的字符串与key不同。那么在进入下一次比较时,mid位置的字符串就没有必要进入下一次的比较当中了。个人感觉不减去1,也是可以得到答案的。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马