黑马程序员技术交流社区

标题: 折半查找问题 [打印本页]
作者: 冯大卫    时间: 2014-9-1 16:04
标题: 折半查找问题
  1. class  Demo
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                         int[] arr = {1,2,6,7,15,10,17,12};
  6.                         int index1 = getIndex(arr,10);
  7.                         System.out.println("index1="+index1);
  8.                     bubbleSort(arr);
  9.                         printArray(arr);
  10.                         int index2 = halfSearch(arr,10);
  11.                         System.out.println("index2="+index2);
  12.                 }
  13.                
  14.                  public static int getIndex(int[] arr,int key)
  15.                 {
  16.                          for (int x = 0; x<arr.length; x++)
  17.                          {
  18.                                  if(arr[x]==key)
  19.                                          return x;
  20.                          }
  21.                          return -1;
  22.                 }
  23.                

  25.                
  26.                 public static void bubbleSort(int[] arr)
  27.                 {
  28.                          for (int x = 0; x<arr.length-1; x++)
  29.                          {
  30.                                  for (int y = 0; y<arr.length-x-1; y++)
  31.                                  {
  32.                                          if(arr[y]>arr[y+1])
  33.                                          {
  34.                                                  int temp = arr[y];
  35.                                                  arr[y] = arr[y+1];
  36.                                                  arr[y+1] = temp;
  37.                                          }

  39.                                  }
  40.                          }
  41.            }
  42.            
  43.                 public static void printArray(int[] arr)
  44.             {
  45.                         System.out.print("[");
  46.                         for (int x = 0; x<arr.length; x++)
  47.                         {
  48.                                 if (x!=arr.length-1)
  49.                                         System.out.print(arr[x]+",");
  50.                                 else
  51.                                         System.out.println(arr[x]+"]");
  52.                         }
  53.                 }
  54.                
  55.                 public static int halfSearch(int[] arr,int key)
  56.                 {
  57.                         int min,max,mid;
  58.                         min = 0;
  59.                         max = arr.length-1;
  60.                         mid = (min+max)/2;
  61.                         while(arr[mid]!=key)
  62.                         {
  63.                                 if (key>arr[mid])
  64.                                         min = mid+1;
  65.                                 else if (key<arr[mid])
  66.                                         max = mid-1;
  67.                                 if (min>max)
  68.                                         return -1;
  69.                                 mid = (min+max)/2;
  70.                         }
  71.                         return mid;
  72.                 }
  73. }
复制代码

运行结果：
index1=5
[1,2,6,7,10,12,15,17]
index2=4

index1和index2查询的结果不一样，答案应该是5
也没找出来我折半查找算法那个地方错了。。。郁闷中，求解答
作者: fantacyleo    时间: 2014-9-1 16:11
都没错。你index1用的是未排序的数组，index2用的是排序后的数组，数组在排序前后不一样，排序前10的下标是5，排序后变成了4
作者: 木易在他乡    时间: 2014-9-1 16:38
楼上正解,楼主在想什么



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