1. public class Test7 {
   
2. 
   
3. /**
   
4. * @param args
   
5. */
   
6. public static void main(String[] args) {
   
7. int[] arr ={2,4,5,7,8,19,32,45};
   
8. int index = halfSearch(arr,8);
   
9. int[] array1 = new int[arr.length+1];
   
10. int[] array2 = new int[arr.length-index];
    
11. 
    
12. for(int i=0,j=0;i<index;i++,j++){
    
13. array1[j]=arr[i];
    
14. }
    
15. 
    
16. for(int i=0;i<array1.length;i++){
    
17. System.out.println(array1[i]);
    
18. }
    
19. 
    
20. 
    
21. for(int i=index,j=0;i<arr.length;i++,j++){
    
22. array2[j]=arr[i];
    
23. }
    
24. 
    
25. System.out.println("====");
    
26. array1[index]=8;
    
27. for(int i=index+1,j=0;i<array1.length;i++,j++){
    
28. array1[i]=array2[j];
    
29. }
    
30. 
    
31. for(int i=0;i<array1.length;i++){
    
32. System.out.println(array1[i]);
    
33. }
    
34. 
    
35. 
    
36. 
    
37. 
    
38. 
    
39. }
    
40. public static int halfSearch(int[] arr,int key){
    
41. int min=0;
    
42. int max=arr.length-1;
    
43. int mid=(min+max)/2;
    
44. while(arr[mid]!=key){
    
45. if(arr[mid]<key){
    
46. min=mid+1;
    
47. }else if(arr[mid]>key){
    
48. max=mid-1;
    
49. }
    
50. if(min>max)
    
51. return -1;
    
52. mid=(min+max)/2;
    
53. }
    
54. return mid;
    
55. }
    
56. 
    
57. }

复制代码

上面代码是实现在原数组基础上添置8，并且数组要有序的。数组不可改变长度，所以只能新建了，感觉这样很麻烦，不知道还有没有更好的办法？

1. /*
   
2. 折半查找并插入元素，保持有序，原数组长度不变
   
3. */
   
4. class InsertEle
   
5. {
   
6.         public static void main(String[] args)
   
7.         {
   
8.                 int[] arr={2,34,67,87,98,454};
   
9.                 int index =halfSearch(arr,34);
   
10.                 insertEle(arr,34,index);
    
11.                 printArr(arr);
    
12.         }
    
13.         
    
14.         //折半查找，返回插入位置
    
15.         public static int halfSearch(int[] arr, int key)
    
16.         {
    
17.                 int min = 0;
    
18.                 int max = arr.length-1;
    
19.                 int mid = (min+max)>>1;
    
20.                 while(min<=max)
    
21.                 {
    
22.                         if(key>arr[mid])
    
23.                                 min=mid+1;
    
24.                         else if(key<arr[mid])
    
25.                                 max=mid-1;
    
26.                         else
    
27.                                 return mid;
    
28.                         mid=(min+max)>>1;
    
29.                 }
    
30.                 return min;
    
31.         }
    
32.         
    
33.         //原数组插入，倒序插入，这样可避免元素互换麻烦。
    
34.         //因保证长度不变，原数组最后一个元素自动舍弃
    
35.         public static void insertEle(int[] arr, int key, int index)
    
36.         {
    
37.                 for (int i=arr.length-1; i>index; i--)
    
38.                 {
    
39.                         arr[i]=arr[i-1];                        
    
40.                 }
    
41.                 arr[index]=key;
    
42.         }
    
43.         
    
44.         //打印数组
    
45.         public static void printArr(int[] arr)
    
46.         {
    
47.                 System.out.print("[");
    
48.                 for (int i=0; i<arr.length; i++)
    
49.                 {
    
50.                         if(i!=arr.length-1)
    
51.                                 System.out.print(arr[i]+",");
    
52.                         else
    
53.                                 System.out.println(arr[arr.length-1]+"]");
    
54.                 }
    
55.         }
    
56. }
    
57. 这段代码实现有两个关键点，其中之一是折半查找直接返回的是插入位置，你可以仔细揣摩一下，二是插入时的小技巧，倒序插入，简化代码的同时可以提高效率。

复制代码

doitforyou 发表于 2013-9-27 21:34

大婶 你的方法有bug，会吧最后一位的数覆盖