黑马程序员技术交流社区

标题: 为什么我的折半查找不能返回正确的-1？ [打印本页]
作者: Michael_xpd    时间: 2013-11-27 10:35
标题: 为什么我的折半查找不能返回正确的-1？
本帖最后由 Michael_xpd 于 2013-11-27 14:10 编辑
  1. package Demo;
  2. /**
  3. * 需求：实现折半查找的另一种方法
  4. * 思路：用while循环控制循环折半查找
  5. * 注：当我用小于数组中最大值的整数变量测试时，能返回正确的变量。
  6. *                 当我用大于数组中最大值的整数变量时，不能返回正确的-1
  7. *
  8. *
  9. * */

  11. public class Day0203 {

  13.         public static void main(String[] args) {
  14.                 // TODO 自动生成的方法存根
  15.                 int arr[]={12,33,4,54,8,13,9};
  16.                 sort(arr);
  17.                 System.out.println("排序后");
  18.                 printArray(arr);
  19.                 int index=0;
  20.                 index=halfSort(arr,55);
  21.                 System.out.println(index);

  23.         }
  24.         //定义一个折半查找的功能halfSort()
  25.         public static int halfSort(int arr[],int key){
  26.                 int min=0,max=arr.length,mid;
  27.                 /**int min=0;
  28.                 int max=arr.length;
  29.                 int mid;*/
  30.                 while(min<=max){
  31.                         mid=(min+max)/2;
  32.                         
  33.                         if(arr[mid]<key)
  34.                                 min=mid+1;
  35.                         else if(arr[mid]>key)
  36.                                 max=mid-1;
  37.                         else return mid;        
  38.                 }
  39.                 return -1;
  40.         }
  41.         public static void sort(int arr[]){
  42.                 for(int i=0;i<arr.length;i++){
  43.                         for(int j=i+1;j<arr.length;j++){
  44.                                 if(arr[i]>arr[j]){
  45.                                         arr[i]=arr[i]^arr[j];
  46.                                         arr[j]=arr[i]^arr[j];
  47.                                         arr[i]=arr[i]^arr[j];
  48.                                 }
  49.                         }
  50.                 }
  51.         }
  52.         public static void printArray(int arr[]){
  53.                 for(int i=0;i<arr.length;i++){
  54.                         System.out.print(arr[i]+",");
  55.                 }
  56.                 System.out.println();
  57.         }

  59. }
复制代码
作者: 帅气的冬瓜    时间: 2013-11-27 11:04
                int index=0;
                index=halfSort(arr,55);  // 这行错了，key的值不在范围内。你再试试            
               System.out.println(index);


作者: 殷挥笔    时间: 2013-11-27 11:07
把halfSort方法改成
  1. public static int halfSort(int[] arr,int key)
  2.         {
  3.                 int min =0,max =arr.length-1,mid;
  4.                 while(min <= max)
  5.                 {
  6.                         mid =(min + max)/2;
  7.                         if(key > arr[mid])
  8.                                 min = mid +1;
  9.                         else if(key < arr[mid])
  10.                                 max = mid -1;
  11.                         else
  12.                                 return mid;
  13.                 }
  14.                 return -1;
  15.         }
复制代码

你的max值定义错了，应该是int max = arr.length - 1;你定义的int max = arr.length；会报异常，数组是从0角标开始，所以最大角标比数组长度少1。
作者: ixiangfeng    时间: 2013-11-27 11:08
max应该为arr.length-1吧

这个问题毕老师视频里面讲解过 我说下我的理解
折半查找主要理解两个问题：1.折半的条件（何时该继续折半）;2.折半角标的变化（需要折半后max、min、和mid的关系）
折半条件有两个：1. while(arr[mid] !=key){ if(min > max ) return -1;}      
                         2.while(min <= max){}

折半角标变化：1.当arr[mid]>key时，即key在数组前半段，故应将max移到前面，即max=mid-1;
                     2.当arr[mid]<key时，即key在数组后半段，故应将min移到后面，即min=mid+1;
作者: 李文帅    时间: 2013-11-27 12:19
先说一下代码如何修改，和二楼三楼的修改方法是一样的
应把"max = arr.length;"改为"max = arr.length-1"因为min和max存放的是数组的第一元素和最后一个元素的下标，而数组的最后一个元素下标是arr.length-1
以下是我自己对楼主运行结果的分析和理解：
1、楼主第一次传递一个小于数组最大值时返回了正确结果，未报异常
这是因为传递的值小于数组最大值，即key < arr[max-1](max = arr.length),程序最多访问到
arr[max-1]，不会访问到arr[max]，所以程序不会出现数组下标越界
1.楼主第二次传递的值大于数组最大值，程序报异常
这是因为传递的值大于数组最大值，即key >arr[max-1](max = arr.length) ,程序循环运算
最终会访问到arr[max],此时就出现了数组下标越界，程序停止运行
这是我自己的理解，希望对你有所帮助



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