黑马程序员技术交流社区

标题: 折半查找的问题 [打印本页]

---

作者: 崔玉朋    时间: 2012-7-4 16:20
标题: 折半查找的问题


//为什么我运行着加粗的那句话在这和在while里面的结果都一样呢？
public class HalfSearch {
        public static int half_2(int []arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length;
                mid = (min+max)/2;
                while(min<max)
                {        
                        if(key>arr[mid])
                                min = mid+1;
                        else if(key<arr[mid])
                                max = mid-1;
                        else
                                return mid;
                }
                return -1;
        }
public static void main(String[] args) {
               
                int [] arr = {2,3,5,6,8,9,12,35};
                int num2 = half(arr,12);
                System.out.print(num2);

        }

}

---

作者: 程有愿    时间: 2012-7-4 16:28
你这个里面的min和max的值在引入实参arr的时候就已经为定值了，当然在局部变量和成员变量都可以的，没什么影响

---

作者: 韦念欣    时间: 2012-7-4 16:29


mid = (min+max)/2;
这个语句必须放在循环里面，否则是错误的。
折半查找中的折半操作，就是考这条语句来实现的了，如果你不写在循环里，那么你只能折半一次，而不能连续的折半。
楼主可以使用更多的数据来测试看看结果，就明白了。

---

作者: 田向向    时间: 2012-7-4 16:33


折半查找，max = arr.length-1；并且你在循环语句里面也忘了折半：在if(key>arr[mid])前面加一句mid = (min+max)/2;。主函数里面应该是int num2=half_2(arr,12);,而不是 int num2 = half(arr,12);。：min;mid和max代表的是角标，角标从0开始，arr.length是数组的长度，以前我在这方面糊涂的时候，刘蕴学版主给我说过这么一句话：你把角标当成编号，这个编号是从0开始，在把len当成存在的数量，那他就只能是从1开始，因为0表示没有。把它告诉你，希望你能明白。
整理后的代码：
public class HalfSearch {
         public static int half_2(int []arr,int key)
         {
                 int min,max,mid;
                 min = 0;
                 max = arr.length-1;
                 mid = (min+max)/2;
                 while(min<max)
                 {        
                      mid = (min+max)/2;
                        if(key>arr[mid])
                                 min = mid+1;
                         else if(key<arr[mid])
                                 max = mid-1;
                         else
                                 return mid;
                 }
                 return -1;
         }
public static void main(String[] args) {
                 
                int [] arr = {2,3,5,6,8,9,12,35};
                 int num2 = half_2(arr,12);
                 System.out.print(num2);

        }

}

纯手工，希望对你有所帮助，，要是哪里有不对的请拍砖

---

作者: 王明明    时间: 2012-7-4 16:47


class Demo {
        public static int half(int []arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length;
                while(min<=max)//加上=的号的原因是 当你查找的是2字符的时候 你会发现没加=号 会返回-1 因为min==0 max在mid-1的时候也成了0
                {        
                        mid = (min+max)/2;//必须把mid的计算放在循环里面
                        if(key>arr[mid])
                                min = mid+1;
                        else if(key<arr[mid])
                                max = mid-1;
                        else
                                return mid;
                }
                return -1;
        }
public static void main(String[] args) {
               
                int [] arr = {2,3,5,6,8,9,12,35};
                int num2 = half(arr,2);
                System.out.print(num2);

        }

}
或者也可以这样
class Demo {
        public static int half(int []arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length;
    boolean num = true;
                while(num)
                {        
      mid = (min+max)/2;
                        if(key>arr[mid])
                                min = mid+1;
       else if(key<arr[mid])
                                max = mid-1;
      else if (key == arr[mid])
                                return mid;
      else
       num = false;
                }
                return -1;
        }
public static void main(String[] args) {
               
                int [] arr = {2,3,5,6,8,9,12,35};
                int num2 = half(arr,2);
                System.out.println(num2);
        }
}

---

作者: 崔玉朋    时间: 2012-7-4 17:47

田向向 发表于 2012-7-4 16:33
折半查找，max = arr.length-1；并且你在循环语句里面也忘了折半：在if(key>arr[mid])前面加一句mid = (min ...

ok，谢谢

---

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

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