public static void main(String[] args)
        {
                int[] arr = {1,2,5,9,52,64,65};
                int index = getindex(arr,3);
                System.out.println("index="+index);       

        }
                public static int getindex(int[] arr,int key)
        {
                int min=0,max=arr.length-1,mid;
                while(min<=max)
                {
                        mid = (max+min)/2;
                        if(key>arr[mid])
                                min=mid+1;
                        else if(key<arr[mid])
                                max=min-1;
                        else return mid;
                }
                return min;
      编写的程序如上，程序的作用是用折半查找的方法，确定一个数在数组中的位置，及找到它的角标。我定义的一个数组有有序的数组，程序运行后，当输入10时能正确返回角标index=4；但是当输入3时，理论上角标应该是2，但是输出的index=0；这是为什么啊？

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

复制代码

1. public static int getIndex(int[] arr,int key)
   
2.         {
   
3.                 //1，定义三个变量，记录头角标、尾角标，中间角标。
   
4.                 int min,mid,max;
   
5.                 min = 0;
   
6.                 max = arr.length-1;
   
7.                 mid = (max+min)/2;//(max+min)>>1;
   
8.                 //2，因为不断折半，通过循环完成，只要没有找到就继续循环。
   
9.                 while(arr[mid]!=key)
   
10.                 {
    
11.                         //3，判断中间角标和key的大或者小。
    
12.                         if(key>arr[mid])
    
13.                         {
    
14.                                 min = mid + 1;//小角标改变。
    
15.                         }
    
16.                         else if(key<arr[mid])
    
17.                         {
    
18.                                 max = mid - 1;//大角标改变
    
19.                         }
    
20. 
    
21.                         //4,判断元素不存在的情况，只要小角标大于了大角标，就折半结束，并返回-1，标示不存在的情况。
    
22.                         if(min>max)
    
23.                                 return -1;
    
24. 
    
25.                         //因为max或者min的变化。重新计算mid值。
    
26.                         mid = (max + min) >> 1;
    
27.                 }
    
28. 
    
29.                 return mid;
    
30. 
    
31.         }

复制代码

对比一下和你的程序有什么不同，对比一下就找到答案了

你写错个东西

霍振鹏 发表于 2014-3-25 21:10
你写错个东西

谢谢你啊 果然是写错了一个东西，太给力了:handshake

leon_hm 发表于 2014-3-25 20:41

谢谢你啊 知道了

李东梁 发表于 2014-3-25 20:42
对比一下和你的程序有什么不同，对比一下就找到答案了

哥们你学的真扎实啊 我很惭愧……你用的应该是毕老师讲的第一种方法，谢谢你的标注，你的代码我也仔细看了。谢谢你

        public static int getindex(int[] arr, int key) {
                int min = 0, max = arr.length - 1, mid;
                while (min <= max) {
                        mid = (max + min) / 2;
                        if (key > arr[mid])
                                min = mid + 1;
                        else if (key < arr[mid])
                                max = mid - 1;//兄弟注意细节呀min-1改成mid-1
                        else
                                return mid;
                }
                return min;
        }