1. int [] arr={1,5,6,7};给定一个函数。假如key=8这个函数如何在下面循环中运行的 代码运行顺序。。
   

复制代码

1. 
   
2. public static int halfSearch(int [] arr,int key)
   
3.         {
   
4.                 int max ,min,mid;
   
5.                 max=arr.length-1;
   
6.                 min=0;
   
7.                 mid=(max+min)/2;
   
8.                 while (key!=arr[mid])
   
9.                 {
   
10.                        
    
11.                         if (key>arr[mid])
    
12.                                 min=mid+1;
    
13.                         else if (key<arr[mid])
    
14.                                 max=mid-1;
    
15.                         
    
16. mid=(max+min)/2;
    
17.                
    
18.                 }
    
19. 
    
20.                 return mid;

复制代码

int [] arr={1,5,6,7};
max=3
min=0
mid=3+0/2=1
第一次运行；8!=arr[1]=5  8>5
min=1+1
mid=2+3/2=2
第2次运行； 8!=arr[2]=6
8>6
min =2+1
mid=3+3/2=3
第3次运行； 8!=arr[3]=7
8>7
min=3+1
mid=4+3/2=3
第4次运行； 8!=arr[3]=7
8>7
min=3+1
mid=4+4/2=4
第5次运行；8!=arr[4]这个时候角标已经越界。怎么还能运行
8>arr[4] 没有这个角标。

会调试程序吗？像这类问题，你要学会调试就行

二分查找吧，哥们，你忽略了一种情况，如果min<max呢？
我改写了你的代码，你把

1. if(min<max)
   
2.                                 return -1;//没有找到

复制代码

这句话注释掉就可以查看每次循环输出的结果，然后你就会发现原因的
附上一代代码：

1. 
   
2. public class HalfFind {
   
3. 
   
4.         public static void main(String[] args) {
   
5.                 int [] arr={1,5,6,7};
   
6.                 System.out.println(halfSearch2(arr, 8));
   
7.         }
   
8. 
   
9.         public static int halfSearch(int[] arr, int key) {
   
10.                 int max, min, mid;
    
11.                 max = arr.length - 1;
    
12.                 min = 0;
    
13.                 mid = (max + min) / 2;
    
14.                 while (key != arr[mid]) {
    
15.                         System.out.println(min+"\t"+mid+"\t"+max+"\t"+arr[mid]);
    
16.                         if(min<max)
    
17.                                 return -1;//没有找到
    
18.                         if (key > arr[mid])
    
19.                                 min = mid + 1;
    
20.                         else if (key < arr[mid])
    
21.                                 max = mid - 1;
    
22.                         mid = (max + min) / 2;
    
23.                 }
    
24.                 return mid;
    
25. 
    
26.         }
    
27.         public static int halfSearch2(int[] arr, int key) {
    
28.                 int lowerBound = 0;
    
29.                 int upperBound = arr.length - 1;
    
30.                 int curIn;
    
31.                
    
32.                 while(true){
    
33.                         curIn = (lowerBound + upperBound)/2;
    
34.                         if(arr[curIn] == key){
    
35.                                 return curIn;
    
36.                         }else if(lowerBound > upperBound){
    
37.                                 return -1;
    
38.                         }else{
    
39.                                 if(arr[curIn] < key){
    
40.                                         lowerBound = curIn + 1;
    
41.                                 }else{
    
42.                                         upperBound = curIn - 1;
    
43.                                 }
    
44.                         }
    
45.                 }
    
46.         }
    
47. }
    

复制代码

浮出一个美 发表于 2014-1-22 10:31
二分查找吧，哥们，你忽略了一种情况，如果min

哦 我知道哪里错。~

如果查找不到的话应该会出现一种min > max的情况吧，楼上的朋友是不是写反了？