黑马程序员技术交流社区

标题: binarySearch的返回插入位置 [打印本页]

---

作者: 歌诗王道    时间: 2014-4-13 22:07
标题: binarySearch的返回插入位置

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;
   
9.         String str = list.get(mid);
   
10.         int num = str.compareTo(key);
    
11.         if(num>0)
    
12.            max = mid - 1;
    
13.         else if(num<0)
    
14.            min = mid + 1;
    
15.         else
    
16.            return mid;
    
17.      }
    
18.      return -min-1;
    
19. }

复制代码

以上代码是模拟写的一个collections中的binarySearch方，最后返回的是插入位置的负数再减一。二分法在遍历到最后一个元素时不是mid，max，min三个变量指向一个元素吗，返回的插入位置能为max或者mid吗？

---

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

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