黑马程序员技术交流社区

标题: 折半查找，程序编译通过不能执行，帮忙找错 [打印本页]

作者: 朱秀梅 时间: 2012-6-12 23:27
标题: 折半查找，程序编译通过不能执行，帮忙找错
这是我的代码
/*
      折半查找
*/
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;
                     }
                     else if ( key > arr[mid] )
                     {
                              left = mid;
                     }
            }
            return -1;
      }
}
编译通过但是达不到要求的结果

作者: 王晓新 时间: 2012-6-12 23:36

class HalfSearch
{
public static void main(String[] args) throws Exception
{
int arr[] = {1,3,5,6,7,9,12,24};
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;
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;
}
}

复制代码

我运行成功了。。你看看

作者: 江南 时间: 2012-6-12 23:36
你的折半查找的函数中的条件语句有错，修改之后如下：
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;

      }

}

作者: 王晓新 时间: 2012-6-12 23:38
{:soso_e100:}毕向东老师java基础视频中专门对折半查找做了讲解，你可以去看看

作者: 王超 时间: 2012-6-12 23:52
正确的是：
else if ( key < arr[mid] )
{
right = mid-1; //当你要查找的数字小于第一次查找的中间值的时候，右边的范围下标就移动到中间值减1的位置，因为不包含中间值
}
else if ( key > arr[mid] )
{
left = mid+1;////当你要查找的数字大于第一次查找的中间值的时候，左边的范围下标就移动到中间值加1的位置}

作者: 葛奎 时间: 2012-6-13 00:09
class Test15
{
      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,24);
            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;
      }
}
//改成这样就行了

作者: 胡大强 时间: 2012-6-13 00:16
      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;
      }
}

}

很明显，当key<arr[mid],说明key在arr【mid】的左边，所以缩小范围后，最右边的right=mid-1,而不是等于mid.
kry>arr[mid]时，原理相同！

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

黑马程序员IT技术论坛 X3.2