黑马程序员技术交流社区

标题: 中间值比较怎么去理解？ [打印本页]

---

作者: 突然世界晴    时间: 2015-3-11 22:38
标题: 中间值比较怎么去理解？

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. 
   
7.                 while(min<=max)
   
8.                 {
   
9.                         mid = (max+min)>>1;//  /2;
   
10. 
    
11.                         String str = list.get(mid);
    
12. 
    
13.                         int num = str.compareTo(key);
    
14.                         if(num>0)
    
15.                                 max = mid -1;     //为什么max=min-1？？？？？？？？？？？？？？？？
    
16.           else if(num<0)
    
17.                                 min = mid + 1; //为什么max=min+1？？？？？？？？？？？？？？？？
    
18.           else
    
19.                                 return mid;
    
20.                 }
    
21.                 return -min-1;  //为什么返回  -min-1？？？？？？？？？？？？？？？？
    
22.         }

复制代码

---

作者: Dark县令    时间: 2015-3-13 00:44
首先你要明确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；希望能帮到你！

---

作者: heima_yjh    时间: 2015-3-13 01:38
compareTo方法的返回值有正数、负数和零。当num不为零时，就说明字符串str与字符串key不相同，也就是mid位置的字符串与key不同。那么在进入下一次比较时，mid位置的字符串就没有必要进入下一次的比较当中了。个人感觉不减去1，也是可以得到答案的。

---

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

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