黑马程序员技术交流社区

标题: 折半查找死循环问题 [打印本页]

---

作者: 吴文龙    时间: 2013-5-29 01:35
标题: 折半查找死循环问题
程序
class  halfsearch
{
public static void main(String[] args)
{
  int[] arr={2,34,4,5,6,76,24,78,90,68,3,37};
  bubble(arr);
  printout(arr);
  int index=gethalf_2(arr,37);
  System.out.println("halfkey="+index);
}
public static int gethalf_2(int[] arr,int key)
{
  int min=0,max=arr.length-1,mid;
  while (min<=max)
  {
   mid=min+max>>1;   if (key>arr[mid])  
   min=mid+1;
   else if (key<arr[mid])
   max=mid-1;
   else
   return mid;
  }
   return -1;
}
  public static void printout(int[] arr)
{
  System.out.print("shuzu:[");
  for (int x=0;x<arr.length ;x++ )
  {
   if (x!=arr.length-1)
   System.out.print(arr[x]+", ");
   else
   System.out.println(arr[x]+"]");
  }
    }
public static void bubble(int[] arr)
{
  for (int x=0;x<arr.length;x++)
  {
   for (int y=0;y<arr.length-x-1;y++)
   {
    if (arr[y]>arr[y+1])
    {
     int temp=arr[y];
     arr[y]=arr[y+1];
     arr[y+1]=temp;
    }
   }
  }
}
}

红色部分改为mid=min+max/2为什么就进入死循环了

---

作者: 神之梦    时间: 2013-5-29 01:48


min+max要加括号再除2，如：（min+max）/2
min+max>>1；之所以可以得出正常答案，是因为运算符"+"的优先级大于">>"
min+max>>1;这条语句是先加后右移，min+max/2；是先max/2再与min相加。
出现死循环的原因是从第二次循环开始一直是min=6，mid=11，max=10，这样11=mid=6+10/2;一直这样循环下去了。。。。。。

---

作者: 廖志强    时间: 2013-5-29 08:21
标准代码
/*
        折半查找，二分查找：
                前提：前提是要查找的数组必须是有序的。
*/
class ArrayTest7
{
        public static void main(String[] args)
        {
                //这个数组是有序的,升序
                int[] arr = {12,34,56,89,112};
       
                               
        }

        /*
                需求：二分查找。
                明确：
                        返回值类型：int
                        参数列表：int[] arr,int value
        */
        public static int getIndex(int[] arr,int value)
        {
                                //定义最小索引位置
                int min = 0;                        //min=0
                //定义最大索引位置
                int max = arr.length-1; //max=4
                //计算中间索引位置
                int mid = (max+min)/2;        //mid=2

                while(arr[mid]!=value)  //arr[mid]!=value
                {
                        if(value>arr[mid])
                        {
                                min = mid + 1;  //min=3
                        }
                        else if(value<arr[mid])
                        {
                                max = mid - 1; //max=2
                        }

                        //如果查不到，就返回-1
                        if(min>max)
                        {
                                return -1;
                        }

                        mid = (max+min)/2; //mid=(3+4)/2=3
                }

                return mid;
        }

}

---

作者: 廖志强    时间: 2013-5-29 08:24
楼主写的是冒泡，折半是不需要换位置的，原理有误

---

作者: 王林涛    时间: 2013-5-29 08:36
亲,你应该加上括号,如果对于位运算符的优先级不确定的时候,你以后写代码最好加上括号
mid=(min+max)/2;
mid=(min+max)>>1; //特别是这个,当你不确定>>和+的优先等级的时候,你应该加上括号

---

作者: 小石头39910    时间: 2013-5-29 09:13
class  halfsearch
{
public static void main(String[] args)
{
  int[] arr={2,34,4,5,6,76,24,78,90,68,3,37};//亲折半查找的第一个前提是数组必须是有序的昂
  bubble(arr);
  printout(arr);
  int index=gethalf_2(arr,37);
  System.out.println("halfkey="+index);
}
public static int gethalf_2(int[] arr,int key)
{
  int min=0,max=arr.length-1,mid;
  while (min<=max)
  {
   mid=min+max>>1; //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 printout(int[] arr)
{
  System.out.print("shuzu:[");
  for (int x=0;x<arr.length ;x++ )
  {
   if (x!=arr.length-1)
   System.out.print(arr[x]+", ");
   else
   System.out.println(arr[x]+"]");
  }
    }
public static void bubble(int[] arr)//你的这个函数是冒泡排序法
{
  for (int x=0;x<arr.length;x++)
  {
   for (int y=0;y<arr.length-x-1;y++)
   {
    if (arr[y]>arr[y+1])
    {
     int temp=arr[y];
     arr[y]=arr[y+1];
     arr[y+1]=temp;
    }
   }
  }
}
/*
*折半查找是每次取中间的数与想要查找的数做比较，如果比所有查找的数大就把所定义的小角标向右移
*反之原理相同，具体的代码如下：
* public static int halfSearch2(int[] arr,int key)
         {
                 int min,max,mid;
                 min=0;
                 max=arr.length-1;
                 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;
         }
         
*
*
*/
}

---

作者: 殇_心。    时间: 2013-5-29 16:48
如果问题已解决，请及时修改分类，否则继续提问，谢谢合作！

---

作者: 吴文龙    时间: 2013-5-29 23:56

廖志强 发表于 2013-5-29 08:21
标准代码
/*
        折半查找，二分查找：

我已经使用冒泡排序了啊,是有顺序的

---

作者: 吴文龙    时间: 2013-5-29 23:57

小石头39910 发表于 2013-5-29 09:13
class  halfsearch
{
public static void main(String[] args)

我已经先输出,然后在冒泡排序了,最后才折半查找的啊

---

作者: 吴文龙    时间: 2013-5-30 00:05

王林涛 发表于 2013-5-29 08:36
亲,你应该加上括号,如果对于位运算符的优先级不确定的时候,你以后写代码最好加上括号
mid=(min+max)/2;
mid ...

你的这个答案最靠谱,但是为什么这个折半查找程序会运行通过呢?
public static int gethalf(int[] arr,int key)
        {
                int max,mid,min;
                min=0;
                max=arr.length-1;
                mid=max+min/2;

                while (arr[mid]!=key)
                {
                        if (key>arr[mid])
                        min=mid+1;
                        else if(key<arr[mid])
                        max=max-1;
                        mid=max+min/2;
                        if (min>max)
                                return -1;
                }
                return mid;

---

作者: 吴文龙    时间: 2013-5-30 00:07

廖志强 发表于 2013-5-29 08:24
楼主写的是冒泡，折半是不需要换位置的，原理有误

定义的数组时无序的,不能冒泡排序,然后再查找吗?亲

---

作者: 吴文龙    时间: 2013-5-30 00:09

神之梦 发表于 2013-5-29 01:48
min+max要加括号再除2，如：（min+max）/2
min+max>>1；之所以可以得出正常答案，是因为运算符"+"的优先级 ...

你的这个答案最靠谱,但是为什么这个折半查找程序会运行通过呢?
public static int gethalf(int[] arr,int key)
        {
                int max,mid,min;
                min=0;
                max=arr.length-1;
                mid=max+min/2;

                while (arr[mid]!=key)
                {
                        if (key>arr[mid])
                        min=mid+1;
                        else if(key<arr[mid])
                        max=max-1;
                        mid=max+min/2;
                        if (min>max)
                                return -1;
                }
                return mid;
}

---

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

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