黑马程序员技术交流社区

标题: 折半查找问题咨询急！！！ [打印本页]
作者: 涐扪①起奮乧    时间: 2013-11-21 17:47
标题: 折半查找问题咨询急！！！
本帖最后由 涐扪①起奮乧 于 2013-11-22 00:13 编辑
  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
也没找出来我折半查找算法那个地方错了。。。郁闷中，求解答
作者: 汪洋大海    时间: 2013-11-21 17:57
你的程序是对的。
int[] arr = {1,2,6,7,15,10,17,12};
这个数组不是有序的。
你重新排序之后10往前进了一位。
作者: 何丛    时间: 2013-11-21 18:05
你排完序后进行的二分查找，当然和未排序之前不一样
排序后[1,2,6,7,10,12,15,17]
10的下标是4
所以没有错误好么
楼主，不要这么耍我们好波，害我看好久
作者: 涐扪①起奮乧    时间: 2013-11-21 19:02
何丛 发表于 2013-11-21 18:05
你排完序后进行的二分查找，当然和未排序之前不一样
排序后[1,2,6,7,10,12,15,17]
10的下标是4

的确没有理解过来，真的，不存在欺骗，还请见谅。谢谢你的指点。现在一下子明朗了，有时候因为一点小问题，再找就是找不出来问题，不得以才发表的帖子。我下午浪费了一个小时想这道题。最后还没没想出来
作者: freehiker    时间: 2013-11-21 20:43
折半查找有个前提：查找的数组必须是有序的



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