黑马程序员技术交流社区

标题: 数组学习中,折半查找出现的问题求助. [打印本页]
作者: zhuohong_xiao    时间: 2014-7-21 21:11
标题: 数组学习中,折半查找出现的问题求助.
本帖最后由 zhuohong_xiao 于 2014-7-22 16:26 编辑
  1. <div class="blockcode"><blockquote>/*
  2. 需求：
  3. 查找一个元素在数组中的位置

  5. */
  6. class ArrayTest01  
  7. {
  8.         public static void main(String[] args)
  9.         {
  10.                 int [] arr={12,3,45,53,4,56,78,89,9};
  11.                 int [] arr1={1,2,33,45,66,76,79,345};
  12.                
  13.                 //调用getIndex功能，查找45在数组arr中的位置
  14.                 int x = getIndex(arr,45);
  15.                 System.out.println(x);
  16.                
  17.                 //调用getIndex_1功能查找33在数组arr1中的位置
  18.                 x = getIndex_1(arr1,33);
  19.                 System.out.println(x);
  20.                
  21.                 //调用getIndex_2功能查找2在数组arr1中的位置
  22.                 x = getIndex_2(arr1,2);
  23.                 System.out.println(x);
  24.         }


  27.         //折中查找中间值查找的第一种方式
  28.         //定义一个getIndex功能，对元素中的值进行折半查找
  29.         public static int getIndex_1(int [] arr, int key)
  30.         {
  31.                 //折半查找只能运用于有序的数组。无序的数组是不能使用的。
  32.                 int min=0;
  33.                 int max=arr.length-1;
  34.                 int mid=(min+max)/2;
  35.                 //判断中间值是否与key相等，如果相等，要查找的值就是中间值
  36.                 while(arr[mid]!=key)
  37.                 {        
  38.                         //进行中间值的寻找的判断
  39.                         if (key>arr[mid])
  40.                                 min=mid+1;
  41.                         else if (key<arr[mid])
  42.                                 max=mid-1;
  43.                         //重新赋中间值。之后while会再次判断arr[mind]是否等于key。
  44.                         mid=(min+max)/2;
  45.                         if (min>max)
  46.                                 return -1;
  47.                 }
  48.                 return mid;//当while不成立时返回的结果值
  49.         }


  52.         //折中查找中间值的第二种方式
  53.         public static int getIndex_2(int [] arr, int key)
  54.         {
  55.                 int min=0,max=arr.length-1,mid;
  56.                 while (min<=max)
  57.                 {
  58.                         mid=(min+max)/2;
  59.                         if (key>arr[mid])
  60.                         {
  61.                                 min=mid+1;
  62.                         }else if (key<arr[mid])
  63.                         {
  64.                                 max=mid-1;
  65.                         }else return mid;
  66.                 }
  67.                 return -1;
  68.         }

  70.         //定义一个功能查找数在数组中的位置,数组的位置是用脚标表示
  71.         public static int getIndex(int [] arr, int key)        
  72.         {        
  73.                 //要查找数组中的元素就要使用到for语句进行遍历
  74.                 for (int x=0; x<arr.length; x++)
  75.                 {
  76.                         //判断数值中俄值是否与key相等。相等的话就返回该数组的脚标值。也就得到了元素在数组中的位置
  77.                         if (arr[x]==key)
  78.                         {
  79.                                 return x;
  80.                         }
  81.                 }
  82.                 //当元素在数组中找不到的时候，返回一个-1。表明在数组中找不到这个元素。
  83.                 return -1;
  84.         
  85.         }
  86. }
复制代码


结果显示未
2
-1
0
结果显示错误.那位雷锋可以告诉我错在哪里.谢谢.



出的问题。我已经找到。上面代码我也改正。  谢谢楼下的哥们提醒。谢谢啊  
作者: 依然超级赛亚人    时间: 2014-7-21 23:13
显然，第一个结果是正确的。第二个结果错误应该是33行int max=arr.length-1;你好像没有写-1；第三个结果错误点可能是65行你的返回值对象不对，应该返回mid,你看看是这样的吗？
作者: 沐子松/kf    时间: 2014-7-21 23:17
不错哦，学习了　　　　　　　　　　　　
作者: 楚风★憧憬    时间: 2014-7-21 23:33
视频多看几遍应该可以自己写的
作者: 依然超级赛亚人    时间: 2014-7-21 23:39
还有一点没看到，45行if语句的括号后面多了一个分号...
作者: 赤魂者    时间: 2014-7-21 23:50
楼上这么多错误怎么还会编译呢？ 你在看看毕老师的讲折半查找的视频吧。 而且 这个題貌似在一个二维数组中做会很难么？
作者: 依然超级赛亚人    时间: 2014-7-22 00:03
你的getIndex_1()这个方法除了上面说的问题外还有点其他问题，但是暂时我找不出来，你看下面这段代码，替代你的这个防范后应该可行。

public static int getIndex_1(int[] arr,int value) {
                                int min = 0;
                                int max = arr.length-1;
                                int mid = (min+max)/2;

                                while(arr[mid]!=value) {
                                        if(arr[mid]>value) {
                                                max = mid - 1;
                                        }else if(arr[mid]<value) {
                                                min = mid + 1;
                                        }

                                        if(min > max) {
                                                return -1;
                                        }

                                        mid = (min+max)/2;
                                }

                                return mid;
                        }
作者: zhuohong_xiao    时间: 2014-7-22 16:00
本帖最后由 zhuohong_xiao 于 2014-7-22 16:24 编辑
赤魂者 发表于 2014-7-21 23:50
楼上这么多错误怎么还会编译呢？ 你在看看毕老师的讲折半查找的视频吧。 而且 这个題貌似在一个二维数组中 ...

可以编译，说明 语法没有错误，是之间的语意错误。或者拼写错误
作者: zhuohong_xiao    时间: 2014-7-22 16:02
依然超级赛亚人 发表于 2014-7-21 23:13
显然，第一个结果是正确的。第二个结果错误应该是33行int max=arr.length-1;你好像没有写-1；第三个结果错 ...

是这样的。谢谢啊。
作者: zhuohong_xiao    时间: 2014-7-22 16:20
谢谢各位的提醒。谢谢。我找到自己的错误了。我的错误在于我将33行，max=arr.length-1;写成max=arr.length。还有就是将41行的 else if (key<arr[mid])写成 else if (key<arr[min] )   第65行的返回值不对是mid的我写成min。其实都是一些拼写错误。上面的代码我已经改正过来的。可以正确编译。
作者: zhuohong_xiao    时间: 2014-7-22 16:21
楚风★憧憬 发表于 2014-7-21 23:33
视频多看几遍应该可以自己写的

我是自己仿佛看代码，还有就是结合毕老师画的那个图。都是自己在写代码的时候的一些拼写错误。谢谢你们回复。
作者: zhuohong_xiao    时间: 2014-7-22 16:26
依然超级赛亚人 发表于 2014-7-21 23:39
还有一点没看到，45行if语句的括号后面多了一个分号...

哥们。厉害



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