黑马程序员技术交流社区

标题: 折半查找，程序编译通过不能执行，帮忙找错 [打印本页]
作者: 清秋    时间: 2011-11-10 17:15
标题: 折半查找，程序编译通过不能执行，帮忙找错
本帖最后由 清秋 于 2011-11-10 17:16 编辑
  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. }
复制代码
作者: 刘一扬    时间: 2011-11-10 17:51
                    
                        else if ( key < arr[mid] )

                        {

                                right = mid-1;   //

                        }

                        else if ( key > arr[mid] )

                        {

                                left = mid+1;//

                        }
作者: 清秋    时间: 2011-11-10 17:55
刘一扬 发表于 2011-11-10 17:51
else if ( key < arr[mid] )

                        {

也不行呀
作者: 宋文轩    时间: 2011-11-10 19:35
  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. }
复制代码
其他基本是没有问题的 你能给出你运行错误的提示吗？这样比较方便找问题 代码没事。
作者: olkldksl    时间: 2011-11-10 20:18
你这么循环比较不到数组的首位两个元素
在while循环前面加两个判断语句就解决了
if(key == arr[0])
return 0;
if(key == arr[right])
return right;
作者: 清秋    时间: 2011-11-10 20:45
宋文轩 发表于 2011-11-10 19:35
其他基本是没有问题的 你能给出你运行错误的提示吗？这样比较方便找问题 代码没事。 ...

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

我是在控制台编译这个程序的。编译通过，就是执行的时候，没答案，要按Ctrl + C才能退出
作者: 清秋    时间: 2011-11-10 20:47
olkldksl 发表于 2011-11-10 20:18
你这么循环比较不到数组的首位两个元素
在while循环前面加两个判断语句就解决了
if(key == arr[0])

嗯。是这个道理
作者: 清秋    时间: 2011-11-10 20:48
难道是我被书本误导了？？抄来的代码都抄错了。。
作者: 宋文轩    时间: 2011-11-10 20:53
嗯  加上=号基本就没问题了  我做的时候是在循环里面用 if(lift>right)  return -1;
作者: 石宗银    时间: 2011-11-10 21:29
二分法，是嘛，，，  以下是 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:56
石宗银 发表于 2011-11-10 21:29
二分法，是嘛，，，  以下是 Arrays.binarySearch(...) 的 源代码
private static int binarySearch0(int  ...

这代码可读性差了些吧。最后一句不是很明白
作者: 石宗银    时间: 2011-11-10 22:23
本帖最后由 石宗银 于 2011-11-10 22:27 编辑

ai是一个数组，，i 是查找时的起始位置，，j 是 结束位置(不包括)，，k 是 要查的值 ，，
最后一句，，   因为  l =i  ，，  而i 一定是>=0的，，那么  -(l+1)  一定是个负数，，  即上面没return 到正解值，，那么返回一个负数，，
作者: 坚强    时间: 2011-11-10 22:46
  问楼主一个技术性的小问题，你是怎么传上区的代码，还有复制代码功能，有什么编程的啊？
作者: 清秋    时间: 2011-11-10 23:18
本帖最后由 清秋 于 2011-11-10 23:27 编辑
  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.         }

  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;

  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.         }

  42.         /*
  43.                 折半的第二种
  44.         */

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

我一直以为，返回个负数就好了
作者: 清秋    时间: 2011-11-10 23:22
坚强 发表于 2011-11-10 22:46
问楼主一个技术性的小问题，你是怎么传上区的代码，还有复制代码功能，有什么编程的啊？ ...

工具栏里有个 "<>"，就是插入代码。不区分什么编程语言的
作者: 清秋    时间: 2011-11-10 23:22
坚强 发表于 2011-11-10 22:46
问楼主一个技术性的小问题，你是怎么传上区的代码，还有复制代码功能，有什么编程的啊？ ...

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

o 知道了:victory:
作者: 骚灵小情歌    时间: 2011-11-11 10:59
清秋 发表于 2011-11-10 23:18
视频里讲的两种方法，个人觉得，基本没差别

难道你想得出两种结果？
作者: 王新春    时间: 2011-11-11 19:39
你的折半查找的函数中的条件语句有错，修改之后如下：
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;

        }

}



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