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

基础数据结构和算法八:Binary search

发表于: 2013-11-28   作者:sunwinner   来源:转载   浏览:
摘要: Binary search needs an ordered array so that it can use array indexing to dramatically reduce the number of compares required for each search, using the classic and venerable binary search algori

Binary search needs an ordered array so that it can use array indexing to dramatically reduce the number of compares required for each search, using the classic and venerable binary search algorithm. We maintain indices into the sorted key array that delimit the subar- ray that might contain the search key. To search, we compare the search key against the key in the middle of the subarray. If the search key is less than the key in the middle, we search in the left half of the subarray; if the search key is greater than the key in the middle, we search in the right half of the subarray; otherwise the key in the middle is equal to the search key.  This implementation is worthy of careful study. To study it, we start with the recursive version of binary search implementation. This recursive rank() preserves the following properties:

■ If key is in the table, rank() returns its index in the table, which is the same as the number of keys in the table that are smaller than key.

 

■ If key is not in the table, rank() also returns the number of keys in the table that are smaller than key.

public class BinarySearch {

    // precondition: array a[] is sorted
    public static int rank(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] whitelist = In.readInts(args[0]);

        Arrays.sort(whitelist);

        // read key; print if not in whitelist
        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            if (rank(key, whitelist) == -1)
                StdOut.println(key);
        }
    }
}

 Binary search in an ordered array with N keys uses no more than lg N

基础数据结构和算法八:Binary search

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
二叉查找树简介 二叉查找树(Binary Search Tree), 也成二叉搜索树、有序二叉树(ordered binary tree
二叉查找树简介 二叉查找树(Binary Search Tree), 也成二叉搜索树、有序二叉树(ordered binary tree
1. 概念: Binary-search tree(BST)是一颗二叉树,每个树上的节点都有<=1个父亲节点,ROOT节点
折半查找(binary search) 详解及代码 本文地址: http://blog.csdn.net/caroline_wendy/article/deta
这节重点讨论 树的结构的源代码实现。 先做一铺垫,讨论一下二叉树的存储结构。二叉树的存储结构分
笔者最近开始学习了二叉树这种数据结构,于是写出了一个二叉树的实现~ 二叉树真是个好东西 =。= 该
二叉树的一个重要应用就是查找。 二叉搜索树 满足如下的性质: 左子树的关键字 < 节点的关键字 &
Binary Search Jon Bentley以前说过类似的话:“90%的程序猿无法正确实现二分查找算法 就冲着这句话
Binary Search Jon Bentley曾经说过类似的话:“90%的程序员无法正确实现二分查找算法 就冲着这句话
此文为《data abstraction and problem solving with c++》的读书笔记。这里有个图书管理系统模拟的
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号