黑马程序员技术交流社区

标题: 折半查找代码问题 [打印本页]
作者: 孙万利    时间: 2012-11-24 00:38
标题: 折半查找代码问题
public class zhebansearch{
public static void main(String[] args){
  int [] arr= {1,2,3,5,7,11,18};
  
  int y=halfsearch_1(arr,15);//折半查找1
  
  System.out.println("halfsearch_1y = " +y);
   
}


//折半查找必须是有序数组


//折半查找方法1  （采用中间值与要查找的值进行比较）
public static int halfsearch_1(int[] arr,int key){//key为要查找的元素

  int min=0;//最小值
  int max=arr.length-1;//最大值
  int mid=(min+max)/2;//中间值
  while(arr[mid]!=key){
  
   if(key>arr[mid]){
    min=mid+1;
   }else if(key<arr[mid]){
    max=mid-1;
   }
   if(min>max){
    return -1;//查找不到元素返回-1；
   }
     
  }
return mid;
}

}

我要查找15在数组中的位置，代码如上；返回值应该是-1啊！
怎么会这样

zhebanjieguo.jpg (17.22 KB, 下载次数: 76)

zhebanjieguo.jpg
作者: 廖力    时间: 2012-11-24 00:56
肯定的啊
你折半 你的半mid在循环外面定义的
始终是(min+max)/2的位置
始终是死循环啊
  1. public static int binarySearch(int[] array, int key) {
  2.         int low = 0;// 低位
  3.         int high = array.length - 1;// 高位
  4.         int index = -1;// 返回值
  5.         while (low <= high) {
  6.                 int mid = (low + high) / 2;// 中间折半
  7.                 if (array[mid] == key) {
  8.                         index = mid;
  9.                         break;
  10.                 } else if (array[mid] < key) {
  11.                         low = mid + 1;
  12.                 } else {
  13.                         high = mid - 1;
  14.                 }
  15.         }
  16.         return index;// -1为没有找到 大于-1的话是找到的位置
  17. }
复制代码
附上我写的...
作者: 张海涛    时间: 2012-11-24 02:06
在你的代码基础上稍微修改了一下，注意代码的缩进，不然看起来不美观！
在while循环里面用if判断了mid，如果找到则返回mid，如果偏大或者偏小都会继续折半查找，你的问题就出在没有在while里继续折半，代码如下：
public class zhebansearch{
        public static void main(String[] args){
          int [] arr= {1,2,3,5,7,11,18};
          int y=halfsearch_1(arr,11);//折半查找1
          System.out.println("halfsearch_1        y = " +arr[y]);          
        }
        //折半查找必须是有序数组
        //折半查找方法1  （采用中间值与要查找的值进行比较）
        public static int halfsearch_1(int[] arr,int key){//key为要查找的元素
                  int min=0;//最小值
                  int max=arr.length-1;//最大值
                  int mid=(min+max)/2;
                  while(arr[mid]!=key){          
                           if(key>arr[mid]){
                                        min=mid+1;
                           }else if(key<arr[mid]){
                                        max=mid-1;
                           }
                           if(min>max){
                                        return -1;//查找不到元素返回-1；
                           }
                           mid=(min+max)/2;//你少了这一句
                  }
                  return mid;
        }
}
作者: 孙万利    时间: 2012-11-24 09:29
谢谢大家，我知道了！



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