1. /*
   
2.         折半查找
   
3. */
   
4. class HalfSearch
   
5. {
   
6.         public static void main(String[] args)
   
7.         {
   
8.                 int arr[] = {1,3,5,6,7,9,12,24};
   
9.                 //System.out.println(halfSearch( arr, 0, arr.length, 2 ));
   
10.                 int num = halfSearch( arr, 23 );
    
11.                 System.out.println(num);
    
12.         }
    
13.        
    
14.         private static int halfSearch ( int arr[], int key )
    
15.         {
    
16.                 int left, right, mid;
    
17.                 left = 0;
    
18.                 right = arr.length - 1;       
    
19.                 while ( left < right )
    
20.                 {
    
21.                         mid = ( left + right ) / 2;               
    
22.                         if ( key == arr[mid] )
    
23.                         {
    
24.                                 return mid;
    
25.                         }
    
26.                         else if ( key < arr[mid] )
    
27.                         {
    
28.                                 right = mid;
    
29.                         }
    
30.                         else if ( key > arr[mid] )
    
31.                         {
    
32.                                 left = mid;
    
33.                         }
    
34.                 }
    
35.                 return -1;
    
36.         }
    
37. }
    

复制代码

                    
                        else if ( key < arr[mid] )

                        {

                                right = mid-1;   //

                        }

                        else if ( key > arr[mid] )

                        {

                                left = mid+1;//

                        }

刘一扬 发表于 2011-11-10 17:51
else if ( key < arr[mid] )

                        {

也不行呀

1. /*
   
2.         折半查找
   
3. */
   
4. class HalfSearch
   
5. {
   
6.         public static void main(String[] args)
   
7.         {
   
8.                 int arr[] = {1,3,5,6,7,9,12,24};
   
9.                 //System.out.println(halfSearch( arr, 0, arr.length, 2 ));
   
10.                 int num = halfSearch( arr, 23 );
    
11.                 System.out.println(num);
    
12.         }
    
13.         
    
14.         private static int halfSearch ( int arr[], int key )
    
15.         {
    
16.                 int left, right, mid;
    
17.                 left = 0;
    
18.                 right = arr.length - 1;        
    
19.                 while ( left < right )
    
20.                 {
    
21.                         mid = ( left + right ) / 2;               
    
22.                         if ( key == arr[mid] )
    
23.                         {
    
24.                                 return mid;
    
25.                         }
    
26.                         else if ( key < arr[mid] )
    
27.                         {
    
28.                                 right = mid-1;//这
    
29.                         }
    
30.                         else if ( key > arr[mid] )
    
31.                         {
    
32.                                 left = mid+1;//这
    
33.                         }
    
34.                 }
    
35.                 return -1;
    
36.         }
    
37. }

复制代码

其他基本是没有问题的 你能给出你运行错误的提示吗？这样比较方便找问题 代码没事。

你这么循环比较不到数组的首位两个元素
在while循环前面加两个判断语句就解决了
if(key == arr[0])
return 0;
if(key == arr[right])
return right;

宋文轩 发表于 2011-11-10 19:35
其他基本是没有问题的 你能给出你运行错误的提示吗？这样比较方便找问题 代码没事。 ...

将  while ( left < right ) 再改成 while ( left <= right )，应该就没问题了
否则在查找数组最后一个元素时会出错。

我是在控制台编译这个程序的。编译通过，就是执行的时候，没答案，要按Ctrl + C才能退出

olkldksl 发表于 2011-11-10 20:18
你这么循环比较不到数组的首位两个元素
在while循环前面加两个判断语句就解决了
if(key == arr[0])

嗯。是这个道理

难道是我被书本误导了？？抄来的代码都抄错了。。

嗯  加上=号基本就没问题了  我做的时候是在循环里面用 if(lift>right)  return -1;

二分法，是嘛，，，  以下是 Arrays.binarySearch(...) 的 源代码
private static int binarySearch0(int ai[], int i, int j, int k)
    {
        int l = i;
        for(int i1 = j - 1; l <= i1;)
        {
            int j1 = l + i1 >>> 1;
            int k1 = ai[j1];
            if(k1 < k)
                l = j1 + 1;
            else
            if(k1 > k)
                i1 = j1 - 1;
            else
                return j1;
        }

        return -(l + 1);
    }

石宗银 发表于 2011-11-10 21:29
二分法，是嘛，，，  以下是 Arrays.binarySearch(...) 的 源代码
private static int binarySearch0(int  ...

这代码可读性差了些吧。最后一句不是很明白

ai是一个数组，，i 是查找时的起始位置，，j 是 结束位置(不包括)，，k 是 要查的值 ，，
最后一句，，   因为  l =i  ，，  而i 一定是>=0的，，那么  -(l+1)  一定是个负数，，  即上面没return 到正解值，，那么返回一个负数，，

  问楼主一个技术性的小问题，你是怎么传上区的代码，还有复制代码功能，有什么编程的啊？

1. /*
   
2.         折半查找
   
3. */
   
4. class  SearchTest
   
5. {
   
6.         public static void main(String[] args)
   
7.         {
   
8.                 int arr[] = {2,3,44,56,78,300};                //插入8
   
9.                 System.out.println( halfSearch( arr, 3 ) );
   
10.                 System.out.println( halfSearch2( arr, 3 ) );
    
11.         }
    
12. 
    
13.         /*
    
14.                 折半的第一种
    
15.         */
    
16.         private static int halfSearch( int arr[], int key )
    
17.         {
    
18.                 int left,right,mid;
    
19.                 left = 0;
    
20.                 right = arr.length - 1;
    
21.                 mid = ( left + right ) / 2;
    
22. 
    
23.                 while ( arr[mid] != key )
    
24.                 {
    
25.                         if ( key < arr[mid] )
    
26.                         {
    
27.                                 right = mid - 1;
    
28.                         }
    
29.                         else if ( key > arr[mid] )
    
30.                         {
    
31.                                 left = mid + 1;
    
32.                         }
    
33.                         if ( left > right )
    
34.                         {
    
35.                                 return -1;
    
36.                         }
    
37.                         mid = ( left + right ) / 2;
    
38.                 }
    
39.                 return mid;
    
40.         }
    
41. 
    
42.         /*
    
43.                 折半的第二种
    
44.         */
    
45. 
    
46.         private static int halfSearch2 ( int arr[], int key )
    
47.     {
    
48.                 int left, right, mid;
    
49.         left = 0;
    
50.         right = arr.length - 1;        
    
51.         while ( left <= right )
    
52.         {
    
53.                         mid = ( left + right ) / 2;
    
54.                         //mid = ( left + right ) >> 1;
    
55.             if ( key == arr[mid] )
    
56.             {
    
57.                                 return mid;
    
58.             }
    
59.             else if ( key < arr[mid] )
    
60.             {
    
61.                 right = mid - 1;//这
    
62.             }
    
63.             else if ( key > arr[mid] )
    
64.             {
    
65.                                 left = mid + 1;//这
    
66.                         }
    
67.                 }
    
68.                 return -1;
    
69.         }
    
70. }
    

复制代码

视频里讲的两种方法，个人觉得，基本没差别

石宗银 发表于 2011-11-10 22:23
ai是一个数组，，i 是查找时的起始位置，，j 是 结束位置(不包括)，，k 是 要查的值 ，，
最后一句，，    ...

我一直以为，返回个负数就好了

坚强 发表于 2011-11-10 22:46
问楼主一个技术性的小问题，你是怎么传上区的代码，还有复制代码功能，有什么编程的啊？ ...

工具栏里有个 "<>"，就是插入代码。不区分什么编程语言的

坚强 发表于 2011-11-10 22:46
问楼主一个技术性的小问题，你是怎么传上区的代码，还有复制代码功能，有什么编程的啊？ ...

工具栏里有个 "<>"，就是插入代码。不区分什么编程语言的。

清秋 发表于 2011-11-10 23:22
工具栏里有个 ""，就是插入代码。不区分什么编程语言的。

o 知道了:victory:

清秋 发表于 2011-11-10 23:18
视频里讲的两种方法，个人觉得，基本没差别

难道你想得出两种结果？

你的折半查找的函数中的条件语句有错，修改之后如下：
class HalfSearch

{

     public static void main(String[] args)

        {

                int arr[] = {1,3,5,6,7,9,12,24};

                //System.out.println(halfSearch( arr, 0, arr.length, 2 ));

                int num = halfSearch(arr,23);

                System.out.println(num);

        }

        

        private static int halfSearch (int arr[],int key)

        {

               int left, right, mid;

                left = 0;

                right = arr.length - 1;        

                while ( left < right )

                {

                        mid = ( left + right )/ 2;               

                        if ( key == arr[mid] )

                       {

                               return mid;

                        }

                       else if ( key < arr[mid] )

                        {

                               right = mid-1;

                        }

                        else if ( key > arr[mid] )

                        {

                               left = mid+1;

                       }

                }

                return -1;

        }

}