黑马程序员技术交流社区

标题: 用折半查找方法确定一个数在数组中的位置遇到问题了！ [打印本页]
作者: 尐亽粅    时间: 2014-3-25 20:35
标题: 用折半查找方法确定一个数在数组中的位置遇到问题了！
public static void main(String[] args)
        {
                int[] arr = {1,2,5,9,52,64,65};
                int index = getindex(arr,3);
                System.out.println("index="+index);       

        }
                public static int getindex(int[] arr,int key)
        {
                int min=0,max=arr.length-1,mid;
                while(min<=max)
                {
                        mid = (max+min)/2;
                        if(key>arr[mid])
                                min=mid+1;
                        else if(key<arr[mid])
                                max=min-1;
                        else return mid;
                }
                return min;
      编写的程序如上，程序的作用是用折半查找的方法，确定一个数在数组中的位置，及找到它的角标。我定义的一个数组有有序的数组，程序运行后，当输入10时能正确返回角标index=4；但是当输入3时，理论上角标应该是2，但是输出的index=0；这是为什么啊？

作者: leon_hm    时间: 2014-3-25 20:41
  1.         public static int getindex(int[] arr,int key)
  2.         {
  3.                 int min=0,max=arr.length-1,mid;
  4.                 while(min<=max)
  5.                 {
  6.                         mid = (max+min)/2;
  7.                         if(key>arr[mid])
  8.                                 min=mid+1;
  9.                         else if(key<arr[mid])
  10.                                 //max=min-1;
  11.                              max=mid-1;//此处是mid
  12.                         else return mid;
  13.                 }
  14.                 return -min;
  15.         }
复制代码
作者: 李东梁    时间: 2014-3-25 20:42
  1. public static int getIndex(int[] arr,int key)
  2.         {
  3.                 //1，定义三个变量，记录头角标、尾角标，中间角标。
  4.                 int min,mid,max;
  5.                 min = 0;
  6.                 max = arr.length-1;
  7.                 mid = (max+min)/2;//(max+min)>>1;
  8.                 //2，因为不断折半，通过循环完成，只要没有找到就继续循环。
  9.                 while(arr[mid]!=key)
  10.                 {
  11.                         //3，判断中间角标和key的大或者小。
  12.                         if(key>arr[mid])
  13.                         {
  14.                                 min = mid + 1;//小角标改变。
  15.                         }
  16.                         else if(key<arr[mid])
  17.                         {
  18.                                 max = mid - 1;//大角标改变
  19.                         }

  21.                         //4,判断元素不存在的情况，只要小角标大于了大角标，就折半结束，并返回-1，标示不存在的情况。
  22.                         if(min>max)
  23.                                 return -1;

  25.                         //因为max或者min的变化。重新计算mid值。
  26.                         mid = (max + min) >> 1;
  27.                 }

  29.                 return mid;

  31.         }
复制代码

对比一下和你的程序有什么不同，对比一下就找到答案了
作者: 霍振鹏    时间: 2014-3-25 21:10
你写错个东西

002.png (15.76 KB, 下载次数: 17)

002.png
作者: 尐亽粅    时间: 2014-3-25 21:23
霍振鹏 发表于 2014-3-25 21:10
你写错个东西

谢谢你啊 果然是写错了一个东西，太给力了:handshake
作者: 尐亽粅    时间: 2014-3-25 21:25
leon_hm 发表于 2014-3-25 20:41

谢谢你啊 知道了
作者: 尐亽粅    时间: 2014-3-25 21:30
李东梁 发表于 2014-3-25 20:42
对比一下和你的程序有什么不同，对比一下就找到答案了

哥们你学的真扎实啊 我很惭愧……你用的应该是毕老师讲的第一种方法，谢谢你的标注，你的代码我也仔细看了。谢谢你
作者: luoyilan222    时间: 2014-3-25 21:37
        public static int getindex(int[] arr, int key) {
                int min = 0, max = arr.length - 1, mid;
                while (min <= max) {
                        mid = (max + min) / 2;
                        if (key > arr[mid])
                                min = mid + 1;
                        else if (key < arr[mid])
                                max = mid - 1;//兄弟注意细节呀min-1改成mid-1
                        else
                                return mid;
                }
                return min;
        }



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