`
sunwinner
  • 浏览: 202481 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

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

阅读更多

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

分享到:
评论

相关推荐

    C、C++、JAVA数据结构与算法电子书

    数据结构与算法是计算机科学的基础,对于理解和编写高效软件至关重要。C、C++和Java都是广泛使用的编程语言,它们在处理数据结构和算法时各有特点。以下是对这三种语言在数据结构与算法方面的一些关键知识点的详细...

    Java 数据结构与算法+源代码 高清版

    在IT领域,尤其是在软件开发中,数据结构与算法是核心基础,它们直接影响程序的效率、可维护性和设计质量。这份“Java数据结构与算法+源代码高清版”资源旨在帮助开发者深入理解并掌握这些关键概念。 首先,让我们...

    数据结构与算法教程(C++版)实验和课程设计

    - **性能评估**:对不同的数据结构和算法进行时间和空间复杂度的分析,评估其效率。 - **团队合作**:在项目开发过程中,培养团队协作能力,共同完成一个大型项目的设计与实现。 通过本教程的学习,不仅能够掌握...

    数据结构与算法考研习题 学习资料

    数据结构与算法是计算机科学与技术专业的重要组成部分,它们构成了软件开发的基础,是解决复杂问题的关键工具。在考研中,这部分知识的掌握程度往往决定了考生的技术实力和问题解决能力。本学习资料集专注于数据结构...

    java数据结构和算法学习笔记

    通过以上内容的总结,我们可以看出Java数据结构与算法的学习涵盖了从基础知识到具体应用的各个方面,对于软件开发人员来说非常重要。掌握这些知识不仅可以提高代码质量和效率,还能更好地理解和解决实际问题。

    数据结构与算法分析C语言描述

    通过《数据结构与算法分析C语言描述》这本书,读者不仅可以学到丰富的数据结构知识和算法分析技能,还能掌握如何使用C语言实现这些数据结构和算法。本书通过大量的示例代码和实际案例,让理论知识与实践紧密结合,...

    c#数据结构和算法源码

    在IT领域,掌握数据结构和算法是至关重要的,特别是对于编程语言如C#的开发者来说。数据结构是存储和组织数据的方式,而算法是解决问题或执行任务的特定步骤。本资源"**c#数据结构和算法源码**"提供了一个实践学习的...

    数据结构与算法 c

    ### 数据结构与算法 C #### 一、引言 在计算机科学领域,数据结构与算法是两个极其重要的概念。它们不仅是编程的基础,也是解决实际问题的关键。本篇内容将围绕“数据结构与算法 C”这一主题展开,深入探讨数据...

    数据结构与算法分析(C++版)(第二版)习题参考答案

    #### 一、数据结构与算法基础 **知识点1:数据结构的重要性** - 数据结构是计算机科学中的一个核心概念,它涉及如何在计算机中组织和管理数据。 - 选择合适的数据结构对于提高程序的效率至关重要。 - 不同的数据...

    [数据结构与算法]JAVA二叉树题目总结(包含常见题目部分LeetCode题解)

    在IT领域,数据结构与算法是编程基础的重要组成部分,尤其对于Java开发者来说,掌握二叉树这一经典数据结构及其相关的算法至关重要。本资料主要聚焦于Java实现的二叉树问题,特别是那些常出现在面试和在线编程挑战...

    算法分析和数据结构 Python描述版

    - **强大的内置数据结构**:Python提供了一系列内置的数据结构,如列表(list)、元组(tuple)、字典(dict)等,这些数据结构可以直接用于实现复杂的算法和数据结构。 2. **Python在算法实现中的优势**: - **代码...

    数据结构与算法分析_Java语言描述(第3版)完整源码

    数据结构与算法分析是计算机科学中的核心领域,它关乎如何高效地存储和处理数据,以及设计和实现高效的算法。在Java语言中,这些概念尤为重要,因为Java提供了丰富的库和工具来支持各种数据结构和算法的实现。《数据...

    数据结构和算法用C++语言描述算法的讲稿

    数据结构和算法是计算机科学的基础,对于理解和设计高效的软件至关重要。C++作为一种强大的编程语言,以其面向对象的特性以及对底层操作的良好支持,常被用于描述和实现数据结构与算法。本讲稿将深入探讨如何利用C++...

    Java数据结构和算法第二版

    《Java数据结构和算法第二版》是一本深入探讨如何在Java编程环境中应用数据结构和算法的书籍。在软件开发中,理解和熟练运用数据结构与算法是提升程序性能、优化解决方案的关键。下面,我们将详细探讨这些重要的概念...

    数据结构与算法期末考试试卷

    数据结构与算法是计算机科学的基础,它涉及到如何有效地组织和操作数据,以及设计高效解决问题的策略。这份期末考试试卷涵盖了数据结构与算法的关键概念,包括排序、栈、分治法、哈希表、二叉搜索树和算法分析。 1....

Global site tag (gtag.js) - Google Analytics