黑马程序员技术交流社区

标题: 利用折半查找怎么增加元素 [打印本页]
作者: 早知道    时间: 2013-9-27 20:25
标题: 利用折半查找怎么增加元素
本帖最后由 早知道 于 2013-9-27 20:33 编辑
  1. public class Test7 {

  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];

  12. for(int i=0,j=0;i<index;i++,j++){
  13. array1[j]=arr[i];
  14. }

  16. for(int i=0;i<array1.length;i++){
  17. System.out.println(array1[i]);
  18. }


  21. for(int i=index,j=0;i<arr.length;i++,j++){
  22. array2[j]=arr[i];
  23. }

  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. }

  31. for(int i=0;i<array1.length;i++){
  32. System.out.println(array1[i]);
  33. }





  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. }

  57. }
复制代码
上面代码是实现在原数组基础上添置8，并且数组要有序的。数组不可改变长度，所以只能新建了，感觉这样很麻烦，不知道还有没有更好的办法？
作者: doitforyou    时间: 2013-9-27 21:34
本帖最后由 doitforyou 于 2013-9-27 21:35 编辑
  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. 这段代码实现有两个关键点，其中之一是折半查找直接返回的是插入位置，你可以仔细揣摩一下，二是插入时的小技巧，倒序插入，简化代码的同时可以提高效率。
复制代码
作者: 会说话的木头    时间: 2014-6-26 10:55
本帖最后由 会说话的木头 于 2014-6-26 11:17 编辑
doitforyou 发表于 2013-9-27 21:34

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



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2