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

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

    震惊

    震惊

编辑推荐
Binary Search Jon Bentley以前说过类似的话:“90%的程序猿无法正确实现二分查找算法 就冲着这句话
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without c
1. Problem Denition -- Input: Frequencies p1, p2, ... , pn for items 1, 2, ... , n. [Assume i
分析 根结点固定时平衡二叉树个数=左孩子的个数 * 右孩子的个数。又左孩子或右孩子为空是不妨置为1
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n
12. binary search Trees The search tree data structure supports many dynamic-set operations,i
Given n, how many structurally unique BST's (binary search trees) that store values 1...n? Fo
链接: https://oj.leetcode.com/problems/unique-binary-search-trees/ dp[i]表示当n为i时的BST数量
一、结构及性质: 由名字可以知道,BST是二叉树结构,每个节点包含key data, 以及分别指向左,右、父
1. 概念: Binary-search tree(BST)是一颗二叉树,每个树上的节点都有<=1个父亲节点,ROOT节点
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号