练习：有一个有序的数组，想要将一个元素插入到该数组中，还要保证该数组是有序的。如何获取该元素在数组中的位置。

疑问是：定义数组为int[] arr = {0,1,2,3,4,5,6,7,8,9},如果要插入的值为10，那么通过折半查找函数确定的插入位置是9而不是10？。

不要返回-1改成返回min。min的值就是你要插入的角标位置！

如果你的数组里已经有10，你返回min就是返回的是10的角标，把你的新10放进去。数组里面的10往后顺延

eycrckag 发表于 2013-5-17 19:32
如果你的数组里已经有10，你返回min就是返回的是10的角标，把你的新10放进去。数组里面的10往后顺延 ...

把10放进去，应该是挤走了9的位置了！

看看min是不是定义错了

返回角标值应该是10的，楼主贴出代码look下

1. class ArrayTest
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 int[] arr = {0,1,2,3,4,5,6,7,8,9};
   
6.                 int index = getIndex(arr,11);
   
7.                 System.out.println("index="+index);
   
8.                 printArray(arr);
   
9.         }
   
10. 
    
11.         public static void printArray(int []arr)
    
12.         {
    
13.                 for (int x=0;x<arr.length ;x++ )
    
14.                 {
    
15.                         System.out.print(arr[x]+", ");
    
16.                 }
    
17.        
    
18.         }
    
19.         public static int getIndex(int[] arr,int key)
    
20.         {
    
21.                 int min = 0,max = arr.length-1,mid;
    
22. 
    
23.                 while(min<=max)
    
24.                 {
    
25.                         mid = (max+min)/2;
    
26. 
    
27.                         if(key>arr[mid])
    
28.                                 min = mid + 1;
    
29.                         else if(key<arr[mid])
    
30.                                 max = mid - 1;
    
31.                         else
    
32.                                 return mid;
    
33.                 }
    
34.                 return min;
    
35.         }
    
36. }

复制代码

我还准备把数值插入再打印 但是发现我不会。。。囧