黑马程序员技术交流社区

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

---

作者: 睡不够的猪    时间: 2013-9-6 19:53
标题: 折半查找问题


class ZheBan
{
       public static void main(String[] args)
       {
              int[] arr={1,5,8,7,9,11,25,36};
              int x=getIndex(arr,9);
              System.out.println(x);
              System.out.println("hello");
       }

       public static int getIndex(int[] arr,int key)
       {
              int min=0,max=arr.length-1,mid;
              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 min;
       }
}

这段代码应该没有问题吧 因为每次用javac编译都能通过，可是为什么每次用java执行的时候 dos窗口都不动呢？（有点像是dos卡死了。。。）
请问还有没有遇到过这种情况呢 该怎么办呢？？？

---

作者: xiaoxu    时间: 2013-9-6 20:03
首先折半查找是建立在数组有序的基础上的，你这数组是无序的。
然后mid=(min+max)>>2;这条指令有问题，该为mid=(min+max)>>1；右移1位就是除2，移2位是除4

---

作者: 睡不够的猪    时间: 2013-9-6 20:03
晕死 弄错了个数字 折磨了我半天。。。
  mid=(min+max)>>2;
应该是：mid=(min+max)>>1;

---

作者: 高波    时间: 2013-9-6 20:06
你的代码在你求mid值时出错了，好好看看怎样用位移运算吧

1. class ZheBan
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                int[] arr={1,5,8,7,9,11,25,36};
   
6.                int x=getIndex(arr,9);
   
7.                System.out.println(x);
   
8.                System.out.println("hello");
   
9.         }
   
10. 
    
11.         public static int getIndex(int[] arr,int key)
    
12.         {
    
13.                int min=0,max=arr.length-1,mid;
    
14.                while(min<=max)
    
15.                {
    
16.                        //向右移几位，就是除以2的几次幂，你要除以2，右移1位就行
    
17.                      mid=(min+max)>>1;
    
18.                      if(key>arr[mid])
    
19.                               min=mid+1;
    
20.                      else if(key<arr[mid])
    
21.                               max=mid-1;
    
22.                      else
    
23.                               return mid;
    
24.                 }
    
25.                return min;
    
26.         }
    
27. }

复制代码

---

作者: 李锡碧    时间: 2013-9-6 20:06

1. class ZheBan {
   
2.         public static void main(String[] args) {
   
3.                 int[] arr = { 1, 5, 8, 7, 9, 11, 25, 36 };
   
4.                 int x = getIndex(arr, 9);
   
5.                 System.out.println(x);
   
6.                 System.out.println("hello");
   
7.         }
   
8. 
   
9.         public static int getIndex(int[] arr, int key) {
   
10.                 int min = 0, max = arr.length - 1, mid;
    
11.                 while (min <= max) {
    
12.                         mid = (min + max) >> 1;
    
13.                         if (key > arr[mid])
    
14.                                 min = mid + 1;
    
15.                         else if (key < arr[mid])
    
16.                                 max = mid - 1;
    
17.                         else
    
18.                                 return mid;
    
19.                 }
    
20.                 return min;
    
21.         }
    
22. }
    

复制代码

第12行  mid = (min + max) >> 1;

---

作者: 胡志翔    时间: 2013-9-6 20:12
mid=(min+max)>>2;
2改成1,
右移2是除以4
要折半除以2要右移1

---

作者: Bad_Boy    时间: 2013-9-6 20:14
循环条件有问题，是个死循环：
public static int getIndex(int[] arr,int key)
       {
              int min=0,max=arr.length-1,mid=(min + max)/2;
              while(arr[mid]!=key)
              {
                  
                    if(key>arr[mid]){
                             min=mid+1;
                    }else {
                             max=mid-1;
                    }
                            mid=(min+max)/2;
               }
              return min;
       }

---

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

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