黑马程序员技术交流社区

标题: 自己写了两个使用递归实现拆半查找的方法，出问题了，... [打印本页]
作者: 孟浩然    时间: 2012-6-16 21:15
标题: 自己写了两个使用递归实现拆半查找的方法，出问题了，...
本帖最后由 孟浩然 于 2012-6-16 21:57 编辑
  1. /*
  2. 拆半查找 也可以说是二分查找
  3. 思路：先找到数组中的一个中间量，如果我要找的数比中间量大，那么就往中间量的右边继续使用这种方法查找
  4. 如果我要找的数比中间量小，那么就往中间量的左边继续使用这种方法查找

  6. 注意:拆半查找只能针对有序数列

  8. 定义函数：需要参数 一个数组和需要找的数
  9.                   需要返回找到的数的角标
  10. */

  12. class HalfSearch
  13. {
  14.         public static void main(String[] args)
  15.         {
  16.                 int[] arr={1,3,7,9,13};
  17.                 halfSearch_2(0,arr.length,13,arr);
  18.                 //halfSearch_1(arr,13);
  19.                 //System.out.println(index);
  20.         }

  22.         //方法一 传入数组和要查找的数
  23.         public static void halfSearch_1(int[] arr,int x)
  24.         {
  25.                 int min=0;
  26.                 int max=arr.length-1;
  27.                 int mid=(min+max)/2;

  29.                 if(min<=max)
  30.                 {
  31.                         if(x<arr[mid])
  32.                         {
  33.                                 max=mid-1;
  34.                                 halfSearch_1(arr,x);
  35.                         }
  36.                         else if(x>arr[mid])
  37.                         {
  38.                                 min=mid+1;
  39.                                 halfSearch_1(arr,x);
  40.                         }
  41.                         else if(x==arr[mid])
  42.                         {
  43.                                 System.out.println("找到角标为："+mid);
  44.                         }
  45.                 }
  46.                 }


  49.         //方法二 传入最小、最大角标和要找的数以及数组
  50.         public static void halfSearch_2(int min,int max,int x,int[] arr)
  51.         {
  52.                 int mid=(min+max)/2;
  53.                 if(max>=min)
  54.                 {
  55.                         if(arr[mid]>x)
  56.                         {
  57.                                 halfSearch_2(min,mid-1,x,arr);
  58.                         }
  59.                         else if(arr[mid]<x)
  60.                         {
  61.                                 halfSearch_2(mid+1,max,x,arr);
  62.                         }
  63.                         else if(arr[mid]==x)
  64.                         {
  65.                                 System.out.println("找到角标为:"+mid);
  66.                                 //return mid;
  67.                         }

  69.                 }
  70.                
  71.         }

  73.         }



复制代码
就是上面两个方法，我觉得两个方法没有什么本质区别，但是第一个就是不能找到我要找的数，除了数组中间的那个数，第二个方法是用正常；另外两个都能编译通过，第一个运行时报错信息如下:
  1. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  2. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  3. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  4. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  5. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  6. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  7. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  8. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  9. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  10. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  11. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  12. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  13. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  14. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  15. at HalfSearch.halfSearch_1(HalfSearch.java:39)
  16. at HalfSearch.halfSearch_1(HalfSearch.java:39)
复制代码
就是这些 好多的，我就复制了一段，还有个问题就是如过把上面的方法改成可以返回角标的怎么改，我用不好return，希望有人给我改一下，我看看，用手机连笔记本上的网，发个帖子要半个小时，哎 悲剧啊
作者: 赵倩倩    时间: 2012-6-16 21:22
halfSearch_1 写的死循环了，每次都循环的调用 halfSearch_1(arr,x);没有递归跳出的条件


halfSearch_2 每次传入上下标的范围都在缩小，最后可跳出递归
作者: 孟浩然    时间: 2012-6-16 21:39
赵倩倩 发表于 2012-6-16 21:22
halfSearch_1 写的死循环了，每次都循环的调用 halfSearch_1(arr,x);没有递归跳出的条件

方法一不是有 min=mid+1和max=mid-1吗 它的最小角标和最大角标也是在变啊？
作者: 赵倩倩    时间: 2012-6-16 21:41
孟浩然 发表于 2012-6-16 21:39
方法一不是有 min=mid+1和max=mid-1吗 它的最小角标和最大角标也是在变啊？

因为这个并没有传递到下次递归的方法中去。所以，本质是没有效果的
作者: 王晓新    时间: 2012-6-16 21:47
  1. class HalfSearch
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr={1,3,7,9,13};
  6.                 halfSearch_2(0,arr.length,13,arr);
  7.                 int a=halfSearch_1(arr,13);
  8.                 System.out.println(a);
  9.         }

  11.         //方法一 传入数组和要查找的数
  12.         public static int halfSearch_1(int[] arr,int x)
  13.         {
  14.                 int min=0;
  15.                 int max=arr.length-1;
  16.                

  18.                 while(min<=max)//
  19.                 {
  20.                                             int mid=(min+max)/2;
  21.                         if(x<arr[mid])
  22.                         {
  23.                                 max=mid-1;
  24.                         }
  25.                         else if(x>arr[mid])
  26.                         {
  27.                                 min=mid+1;
  28.                         }
  29.                         else
  30.                         {
  31.                                 return mid;
  32.                         }
  33.                 }
  34.                                 return -1;
  35.                 }


  38.         //方法二 传入最小、最大角标和要找的数以及数组
  39.         public static void halfSearch_2(int min,int max,int x,int[] arr)
  40.         {
  41.                 int mid=(min+max)/2;
  42.                 if(max>=min)
  43.                 {
  44.                         if(arr[mid]>x)
  45.                         {
  46.                                 halfSearch_2(min,mid-1,x,arr);
  47.                         }
  48.                         else if(arr[mid]<x)
  49.                         {
  50.                                 halfSearch_2(mid+1,max,x,arr);
  51.                         }
  52.                         else if(arr[mid]==x)
  53.                         {
  54.                                 System.out.println("找到角标为:"+mid);
  55.                         }

  57.                 }
  58.                
  59.         }
  60. }
复制代码
我对你的第一种方法改了一下，希望对楼主有帮助。。
作者: 王明明    时间: 2012-6-16 22:07
具体什么原因上面的都说了
我加一个我用FOR 写的方法
  1. class ceshi2
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr={1,3,7,9,13};
  6.                 //halfSearch_2(0,arr.length,13,arr);
  7.                 halfSearch_1(arr,13);
  8.                 //System.out.println(index);
  9.         }

  11.         //方法一 传入数组和要查找的数
  12.         public static void halfSearch_1(int[] arr,int x)
  13.         {

  15.                 for( int min=0,max=arr.length-1;min<=max;)
  16.                 {               
  17.                                         int mid=(min+max)/2;
  18.        
  19.                         if(x<arr[mid])
  20.                         {
  21.                                 max=mid-1;
  22.                              
  23.                         }
  24.                         else if(x>arr[mid])
  25.                         {
  26.                                 min=mid+1;
  27.                               
  28.                         }
  29.                         else if(x==arr[mid])
  30.                         {
  31.                                 System.out.println("找到角标为："+mid);
  32.                                                                 break;
  33.                         }
  34.                 }
  35.                 }

  37.         }
复制代码
作者: 胡大强    时间: 2012-6-16 23:48
/*
拆半查找 也可以说是二分查找
思路：先找到数组中的一个中间量，如果我要找的数比中间量大，那么就往中间量的右边继续使用这种方法查找
如果我要找的数比中间量小，那么就往中间量的左边继续使用这种方法查找
注意:拆半查找只能针对有序数列
定义函数：需要参数 一个数组和需要找的数
                  需要返回找到的数的角标
*/
class HalfSearch
{
        public static void main(String[] args)
        {
                int[] arr={1,3,7,9,13};
                //halfSearch_2(0,arr.length,13,arr);
                halfSearch_1(arr,13);
                //System.out.println(index);
        }
        //方法一 传入数组和要查找的数
        public static void halfSearch_1(int[] arr,int x)
        {
                int min=0;
                int max=arr.length-1;  ///
               
                while(min<=max)  ///
                {
      int mid=(min+max)/2;   
                        if(x<arr[mid])
                        {
                                max=mid-1;
                               // halfSearch_1(arr,x);
                        }
                        else if(x>arr[mid])
                        {
                                min=mid+1;
                               // halfSearch_1(arr,x);
                        }
                        else if(x==arr[mid])
                        {
                                System.out.println("找到角标为："+mid);
        break;
                        }
                }
    }

    /*    //方法二 传入最小、最大角标和要找的数以及数组
        public static void halfSearch_2(int min,int max,int x,int[] arr)
        {
                int mid=(min+max)/2;
                if(max>=min)
                {
                        if(arr[mid]>x)
                        {
                                halfSearch_2(min,mid-1,x,arr);
                        }
                        else if(arr[mid]<x)
                        {
                                halfSearch_2(mid+1,max,x,arr);
                        }
                        else if(arr[mid]==x)
                        {
                                System.out.println("找到角标为:"+mid);
                                //return mid;
                        }
                }
               
        }*/
        }


///这是修改之后的代码。。。。。。。楼主可对照看一下。。。




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