一个经典的二分查找算法

刺骨的言语ヽ痛彻心扉 2022-07-12 09:16 185阅读 0赞

转 ： [http://www.zhuoda.org/weiking/67932.html][http_www.zhuoda.org_weiking_67932.html]

一个经典的二分查找算法

1:     public static int binarySearch(int[] a, int key) {
       
    2:         int low = 0;
    3:         int high = a.length - 1;
    4: 
    5:         while (low <= high) {
       
    6:             int mid = (low + high) / 2;
    7:             int midVal = a[mid];
    8:
    9:             if (midVal < key)
    10:                 low = mid + 1;
    11:             else if (midVal > key)
    12:                 high = mid - 1;
    13:             else
    14:                 return mid; // key found
    15:         }
    16:         return -(low + 1);  // key not found.
    17:     }
    
    
    很有意思，java.util.Arrays的BUG 。
    
    bug出现在第6行:
    
    6:             int mid =(low + high) / 2;
    
    在一般情况下, 这个语句是不会出错的, 但是, 当low+high的值超过了最大的正int值 (231 - 1) 的时候, mid会变成负值,  这个时候, 会抛出ArrayIndexOutOfBoundsException 异常..
    
    所以当一个数组包含超过2的30次方 个元素的时候, 就很可能会带来问题... 当然, 在一般的应用里面, 很少数组会包含那么多元素, 但是现在这样的情况已经越来越多了, 比如Google的海量运算..
    
    那如何解决这个问题?
    
    很简单, 修改这行语句为:
    
    6:             int mid = low + ((high - low) / 2);
    或者
    6:             int mid = (low + high) >>> 1;
    
    感兴趣的起看看原文：http://www2.matrix.org.cn/resource/news/Joshua+Bloch+Bug_768.html 
       
        weiking   2006-09-25 16:12:03 评论:3   阅读:3769   引用:0 
      
       
       
        很好的一个算法设计，却不被人理解 @2009-03-05 16:03:56  lzc_java@126.com 很好的一个算法设计，楼上的（pi @2008-09-19 21:26:09   ）你理解作者的意思了吗？你知道这句话是什么意思吗？int high = a.length - 1这是指数组长度呀，只要保证数组长度小于2的31次就可以了，而int mid =(low + high) / 2;当所找的key在mid后面，则low=mid+1;当再次经过int mid =(low + high) / 2；这个时候就危险了，很可能此时的low+high超过了2的31次 
       
        无题 @2008-10-25 10:54:20   算法有问题,这个二分查询建立在排序的基础上, 白花时间! 
       
        pi @2008-09-19 21:26:09   屁话，有问题的话这句int high = a.length - 1;中high就得不到正确值了，你后面就是多此一举！！！！

[http_www.zhuoda.org_weiking_67932.html]: http://www.zhuoda.org/weiking/67932.html