当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

binary search

发表于: 2012-01-29   作者:bookjovi   来源:转载   浏览:
摘要:   最近看了关于binary search的一遍blog,blog标题是 "几乎所有的binary search和merge sort都有错",读完感触颇深,点这里。     首先看看sun关于binary search的一个bug报告:   A DESCRIPTION OF THE PROBLEM : java.ut

  最近看了关于binary search的一遍blog,blog标题是 "几乎所有的binary search和merge sort都有错",读完感触颇深,点这里

 

  首先看看sun关于binary search的一个bug报告

 

A DESCRIPTION OF THE PROBLEM :
java.util.Arrays.binarySearch() will throw an ArrayIndexOutOfBoundsException if the array
is large.  This is caused by overflow in the calculation:

           int mid = (low + high) >> 1;

The correct calculation uses unsigned shift:

           int mid = (low + high) >>> 1;

 

 

  比较了一下jdk中binary search和Linux kernel中bsearch的代码:

 

    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

 

 

 

void *bsearch(const void *key, const void *base, size_t num, size_t size,
              int (*cmp)(const void *key, const void *elt))
{
        size_t start = 0, end = num;
        int result;

        while (start < end) {
                size_t mid = start + (end - start) / 2;

                result = cmp(key, base + mid * size);
                if (result < 0)
                        end = mid;
                else if (result > 0)
                        start = mid + 1;
                else
                        return (void *)base + mid * size;
        }

        return NULL;
}

  还好Linux kernel中没有使用: int mid =(low + high) / 2;

 

  不要轻看任何一个小程序,再简单的逻辑也可能有bug。

 

binary search

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号