黑马程序员技术交流社区

标题: 我今天写的一个折半查找，怎么编译过了就是打印不出-1呢？ [打印本页]

---

作者: 欧阳才志    时间: 2012-4-7 21:25
标题: 我今天写的一个折半查找，怎么编译过了就是打印不出-1呢？
/*
作者：
时间：2012年4月7日
功能，查找一个数在一个数组里的脚标
*/
class  demo4
{
        public static void main(String[] args)
        {
                int[] arr={2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,18,19};
                int index=findindexArr(arr,8);//调用函数，并将返回的脚标装起来
                System.out.println("index="+index);//打印返回的脚标
        }
        public static int findindexArr(int [] x,int y)
        {
                int min=0,max=x.length-1,mid;
                while(min<=max)
                {
                            mid=(max+min)/2;
                                if (y>x[mid])
                                        mid=mid+1;
                                else if(y<x[mid])
                                        mid=mid-1;
                                else
                                        return mid;
                }
                return -1;
        }
}

我定义的数组里没有8，返回值应该是-1的啊,怎么不是呢？好奇怪？哪里出了问题？

---

作者: 秦岩    时间: 2012-4-7 21:29

1. 
   
2. public static void main(String[] args) {
   
3.                                 int[] arr={2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,18,19};
   
4.                                 int index=findindexArr(arr,8);//调用函数，并将返回的脚标装起来
   
5.                                 System.out.println("index="+index);//打印返回的脚标
   
6.                         }
   
7.                         public static int findindexArr(int [] x,int y)
   
8.                         {
   
9.                                 int min=0,max=x.length-1,mid;
   
10.                                 while(min<=max)
    
11.                                 {
    
12.                                             mid=(max+min)/2;
    
13.                                                 if (y>x[mid])
    
14.                                                         mid=mid+1;  // 应该这样写    min = mid + 1;
    
15.                                                 else if(y<x[mid])   
    
16.                                                         mid=mid-1;   // 应该这样写    max = mid + 1;
    
17.                                                 else
    
18.                                                         return mid;
    
19.                                 }
    
20.                                 return -1;
    
21. 
    
22.        
    
23.         }

复制代码

if 语句内的错误，我已经标注出来了~~  

---

作者: 宋蕈    时间: 2012-4-7 21:35
标题: 哥地方


class  demo4
{
        public static void main(String[] args)
        {
                int[] arr={2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,18,19};
                int index=findindexArr(arr,8);
                System.out.println("index="+index);
        }
        public static int findindexArr(int [] x,int y)
        {
                int min=0,max=x.length-1,mid;
                while(min<=max)      
                {
                            mid=(max+min)/2;
                                if (y>x[mid])
                                        mid=mid+1;   //  这个地方，你就算把mid设置为了加一，等它
                                                                                                        // 程序执行后一样循环到 mid=(max+min)/2 ，总的来说，程序就一直死循环着，
                                else if(y<x[mid])
                                        mid=mid-1;   //  这个地方也是一样
                                else
                                        return mid;
                }
                return -1;
        }

解决方法：
                  public static int findindexArr(int [] x,int y)
        {
                int min=0,max=x.length-1,mid;
                while(min<=max)      
                {
                            mid=(max+min)/2;
                                if (y>x[mid])
                                        min=mid+1;   // 该为这个
                                                                            
                                else if(y<x[mid])
                                        max=mid-1;   // 该为这个
                                else
                                        return mid;
                }
                return -1;
        }

最后结果就能运行了。

---

作者: 秦岩    时间: 2012-4-7 21:39

宋蕈 发表于 2012-4-7 21:35
class  demo4
{
        public static void main(String[] args)

你回答错了。。晕~~~~


min=x[mid]+1;  这里  不可以写这样。。   这是数组的角标加1  ，不是数组角标对应的数字加1~~~   正确的是： min = mid + 1;

---

作者: 薛飞飞    时间: 2012-4-7 21:40
很简单啊，你while里面的执行语句设置错误，你的min和max从来没变过，进而导致程序死循环：
while的具体代码如下：
while(min<=max)
                {   
                    mid=(min+max)/2 ;
                        if (y>x[mid])
                          min=mid+1;
                      else if(y<x[mid])
                          max=mid-1;
                      else
                          return mid;
                }

---

作者: 张小庆    时间: 2012-4-7 21:49
楼上说的对，你那代码应该是打错了吧

---

作者: 郑强强    时间: 2012-4-7 22:28
楼主以后编程一定要注意循环体的判断条件了

---

作者: 郑强强    时间: 2012-4-7 22:29
楼主以后编程一定要注意循环体的判断条件了

5.JPG (41.03 KB, 下载次数: 51)

下载附件

2012-4-7 22:28 上传

---

作者: 文密    时间: 2012-4-7 23:07
  注意循环体的判断条件

public static int findindexArr(int [] x,int y)
        {
                int min=0,max=x.length-1,mid;
                while(min<=max)
                {
                            mid=(max+min)/2;
                                if (y>x[mid])
                                        mid=mid+1;       //改为min = mid + 1
                                else if(y<x[mid])
                                        mid=mid-1;        // 改为max = mid - 1
                                else
                                        return mid;
                }
                return -1;
        }

---

作者: 欧阳才志    时间: 2012-4-8 12:13
谢谢啊！我知道了！怎么没有看到这里呢，哈哈！

---

作者: 欧阳才志    时间: 2012-4-8 12:32


/*
作者：
时间：2012年4月7日
功能，寻找一个数在一个有序数组里的位置，并打印出脚标，如果找不到，返回-1
*/
class  demo4
{
        public static void main(String[] args)
        {
                int[] arr={2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
                int index=insertArr(arr,8);
                System.out.println("index="+index);
        }
        public static int insertArr(int [] x,int y)
        {
                int min=0,max=x.length-1,mid;
                while(min<=max)
                {
                            mid=(max+min)/2;//将数组的脚标分成两半，中间的那个脚标先标记起来
                                if (y>x[mid]) //所给值大于这个有序数组的中间值，那么我就应该在这个有序数组的后边找，
                                        {min=mid+1;}//脚标最小值移到中间值后边第一位
                                else if(y<x[mid])
                                        {max=mid-1;}//小于数组中的中间值时，应该往前找，将脚标最大值移到中间值前一位
                                else
                                        return mid;// 中奖，我给的值正好就是中间这个
                }
                return -1;
        }
}
修改了一下，呵呵，结果正确。哎！怎么会没有发现问题在这里呢？晕菜！谢谢各位了！

---

作者: pray    时间: 2014-4-26 04:38
我也来顶一下..

---

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

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