1. <p>class Demo{
   
2.         static int halfsearch(int arr[],int key){
   
3.                 int min=0;
   
4.                 int max=arr.length;
   
5.                 int mid=(min+max)/2;
   
6.                 while(min<=max){
   
7.                         mid=(min+max)/2;
   
8.                         if(key>arr[mid])
   
9.                         {
   
10.                                 min=mid+1;
    
11.                         }
    
12.                         else if(key<arr[mid])
    
13.                         {
    
14.                                 max=mid-1;
    
15.                         }
    
16.                         else
    
17.                                 return mid;
    
18.                 }
    
19.                 return mid;
    
20.         }
    
21.         /**
    
22.          * 在一个有序数组中利用折半查找的思想，来插入一个元素，使得插入后的数组依然有序，代码实现返回插入的位置。
    
23.          * */
    
24.         public static void main(String args[]){
    
25.                 int arr[]={1,2,4,5,6,7,9};       
    
26.                
    
27.                 System.out.print(halfsearch(arr,-1));//这程序有个问题就是当要插入的数比数组中的最大元素大时，会发生数组角标越界的情况
    
28. 
    
29.         }
    
30. }</p><p>要如何修改呢？
    
31. </p>

复制代码

1. class Demo
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5. 
   
6.                 int[] arr = new int[]{1,6,9,11,18,54,60,66,90};
   
7.                 System.out.println("insert 19 to array:");
   
8.                 printArr(arr);
   
9.                 int[] newArr = insert( arr, 100 );
   
10.                 printArr( newArr );
    
11. 
    
12.         }
    
13. 
    
14.         //打印一个数组
    
15.         public static void printArr(int[] arr)
    
16.         {
    
17.                 for (int x = 0; x<arr.length; x++ )
    
18.                 {
    
19.                         if (x == arr.length - 1)
    
20.                         {
    
21.                                 System.out.println(arr[x]);
    
22.                                 break;
    
23.                         }
    
24.                         System.out.print(arr[x] + "\t");
    
25.                 }
    
26.         }
    
27. 
    
28.         //在数组中插入一个元素
    
29.         public static int[] insert( int[] arr, int insertKey )
    
30.         {
    
31.        
    
32.         int loc, mid;
    
33.         int[] newArr = new int[arr.length + 1];
    
34. 
    
35.         mid = locFind( arr, insertKey );
    
36. 
    
37.         //插入新元素操作，分三种情况，在首部，在尾部，在中间
    
38.         if (insertKey < arr[0])//在首部
    
39.         {
    
40.                 newArr[0] = insertKey;
    
41.                 for ( int x = 1; x <= arr.length; x++ )
    
42.                 {
    
43.                         newArr[x] = arr[x - 1];
    
44.                 }
    
45.         }
    
46.         else if (insertKey > arr[arr.length - 1])//在尾部
    
47.         {
    
48.                 int x;
    
49.                 for (x = 0 ; x < arr.length ; x++ )
    
50.                 {
    
51.                         newArr[x] = arr[x];
    
52.                 }
    
53.                 newArr[x] = insertKey;
    
54.         }
    
55.         else//在中间
    
56.         {
    
57.                 for ( loc = 0; loc <= mid; loc++ )//插入位之前的元素赋值给新数组
    
58.                 {
    
59.                         newArr[loc] = arr[loc];
    
60.                 }
    
61. 
    
62.                 newArr[loc] = insertKey;
    
63.                
    
64.                 for ( loc++; loc < newArr.length; loc++ )//插入位之后的元素赋值给新数组
    
65.                 {
    
66.                         newArr[loc] = arr[loc - 1];
    
67.                 }
    
68. 
    
69.         }
    
70. 
    
71.         return newArr;
    
72. 
    
73.         }
    
74. 
    
75. 
    
76.         //用折半查找法找到元素应该插入数组的位置并返回
    
77.         public static int locFind( int[] arr, int insertKey )
    
78.         {
    
79. 
    
80.         int min, mid, max;
    
81. 
    
82.         min = 0;
    
83.         max = arr.length;
    
84.         mid = ( max + min ) / 2;
    
85. 
    
86.         while ( min < max )
    
87.         {
    
88.                 if ( insertKey > arr[mid] )
    
89.                 {
    
90.                         min = mid + 1;
    
91.                 }
    
92.                 else if ( insertKey < arr[mid] )
    
93.                 {
    
94.                         max = mid - 1;
    
95.                 }
    
96. 
    
97.                 mid = ( max + min ) / 2;
    
98.         }
    
99. 
    
100.         return mid;
     
101. 
     
102.         }
     
103. }

复制代码

经过我的修改，代码已经可以实现了，原来要分成三种情况来判断插入的位置~

关于越界图解