1. /*
   
2. 拆半查找 也可以说是二分查找
   
3. 思路：先找到数组中的一个中间量，如果我要找的数比中间量大，那么就往中间量的右边继续使用这种方法查找
   
4. 如果我要找的数比中间量小，那么就往中间量的左边继续使用这种方法查找
   
5. 
   
6. 注意:拆半查找只能针对有序数列
   
7. 
   
8. 定义函数：需要参数 一个数组和需要找的数
   
9.                   需要返回找到的数的角标
   
10. */
    
11. 
    
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.         }
    
21. 
    
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;
    
28. 
    
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.                 }
    
47. 
    
48. 
    
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.                         }
    
68. 
    
69.                 }
    
70.                
    
71.         }
    
72. 
    
73.         }
    
74. 
    
75. 
    
76. 
    

复制代码

就是上面两个方法，我觉得两个方法没有什么本质区别，但是第一个就是不能找到我要找的数，除了数组中间的那个数，第二个方法是用正常；另外两个都能编译通过，第一个运行时报错信息如下:

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，希望有人给我改一下，我看看，用手机连笔记本上的网，发个帖子要半个小时，哎 悲剧啊

halfSearch_1 写的死循环了，每次都循环的调用 halfSearch_1(arr,x);没有递归跳出的条件


halfSearch_2 每次传入上下标的范围都在缩小，最后可跳出递归

赵倩倩 发表于 2012-6-16 21:22
halfSearch_1 写的死循环了，每次都循环的调用 halfSearch_1(arr,x);没有递归跳出的条件

方法一不是有 min=mid+1和max=mid-1吗 它的最小角标和最大角标也是在变啊？

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

因为这个并没有传递到下次递归的方法中去。所以，本质是没有效果的

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.         }
   
10. 
    
11.         //方法一 传入数组和要查找的数
    
12.         public static int halfSearch_1(int[] arr,int x)
    
13.         {
    
14.                 int min=0;
    
15.                 int max=arr.length-1;
    
16.                
    
17. 
    
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.                 }
    
36. 
    
37. 
    
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.                         }
    
56. 
    
57.                 }
    
58.                
    
59.         }
    
60. }

复制代码

我对你的第一种方法改了一下，希望对楼主有帮助。。

具体什么原因上面的都说了
我加一个我用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.         }
   
10. 
    
11.         //方法一 传入数组和要查找的数
    
12.         public static void halfSearch_1(int[] arr,int x)
    
13.         {
    
14. 
    
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.                 }
    
36. 
    
37.         }

复制代码

/*
拆半查找 也可以说是二分查找
思路：先找到数组中的一个中间量，如果我要找的数比中间量大，那么就往中间量的右边继续使用这种方法查找
如果我要找的数比中间量小，那么就往中间量的左边继续使用这种方法查找
注意:拆半查找只能针对有序数列
定义函数：需要参数 一个数组和需要找的数
                  需要返回找到的数的角标
*/
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;
                        }
                }
               
        }*/
        }


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