A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

这是我的代码
/*
        折半查找
*/
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;
        }
}
编译通过但是达不到要求的结果

评分

参与人数 1技术分 +1 收起 理由
黄奕豪 + 1 赞一个!

查看全部评分

7 个回复

倒序浏览

回帖奖励 +10

  1. class HalfSearch
  2. {
  3.         public static void main(String[] args) throws Exception
  4.         {
  5.                 int arr[] = {1,3,5,6,7,9,12,24};
  6.                 int num = halfSearch( arr, 23 );
  7.                 System.out.println(num);
  8.         }      
  9.         private static int halfSearch ( int arr[], int key )
  10.         {
  11.                 int left, right, mid;
  12.                 left = 0;
  13.                 right = arr.length;        
  14.                 while ( left < right )
  15.                 {
  16.                         mid = ( left + right ) / 2;               
  17.                         if ( key == arr[mid] )
  18.                         {
  19.                                 return mid;
  20.                         }
  21.                         else if ( key < arr[mid] )
  22.                         {
  23.                                 right = mid-1;
  24.                         }
  25.                         else if ( key > arr[mid] )
  26.                         {
  27.                                 left = mid+1;
  28.                         }
  29.                 }
  30.                 return -1;
  31.         }
  32. }
复制代码
我运行成功了。。你看看

评分

参与人数 1技术分 +1 收起 理由
黄奕豪 + 1 赞一个!

查看全部评分

回复 使用道具 举报
你的折半查找的函数中的条件语句有错,修改之后如下:
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;

        }

}

评分

参与人数 1技术分 +1 收起 理由
黄奕豪 + 1 赞一个!

查看全部评分

回复 使用道具 举报
{:soso_e100:}毕向东老师java基础视频中专门对折半查找做了讲解,你可以去看看
回复 使用道具 举报
正确的是:
else if ( key < arr[mid] )
{
right = mid-1;  //当你要查找的数字小于第一次查找的中间值的时候,右边的范围下标就移动到中间值减1的位置,因为不包含中间值
}
else if ( key > arr[mid] )
{
left = mid+1;////当你要查找的数字大于第一次查找的中间值的时候,左边的范围下标就移动到中间值加1的位置}
回复 使用道具 举报
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;
        }
}
//改成这样就行了
回复 使用道具 举报
        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]时,原理相同!


回复 使用道具 举报
我运行你的代码 发现 你的程序 在 left=6, right=7 也就是 在12 和 24 这两个数之间不停的循环 ,程序进入了死循环
你发现没有 这时候你的CPU是消耗很大的,因为程序进入了死循环不停的在 12 和24 之间做比较
为什么呢?我给你分析一下
第一次
left=0 right=7  mid=3, 对应的分别是  1,24,6,  arr[mid]=6  显然23>arr[mid]   
第二次
left=3, right=7, mid=5,对应的分别是 6,24,9, arr[mid]=9 显然 23>arr[mid]
第三次
left=5,right=7,mid=6, 对应的分别是9,24,12,   arr[mid]=12 ,显然23>arr[mid]
第四次
left=6,right=7,mid=6,对应的分别是12,24,12    arr[mid]=12 ,显然23>arr[mid]
第五次
left=6,right=7,mid=6,对应的分别是12,24,12    arr[mid]=12 ,显然23>arr[mid]
。。。
。。。
。。。
所以循环一直 在这里循环
所有没有结果 永远这样循环下去,知道天荒地老!
解决的办法是 你应该这样写
right=mid-1
left=mid+1
因为当你判断 (key<arr[mid])  或者 (key>arr[mid]) 时
arr[mid] 这个数已经比较过了,所有索引 right, left就必须 移动 要么减一 要么加一
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马