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
相关推荐
TestBinarySearchTree.cpp: Test program for binary search tree AvlTree.h: AVL tree TestAvlTree.cpp: Test program for AVL trees mapDemo.cpp: Map demos WordLadder.cpp: Word Ladder Program and Word ...
数据结构常用算法c++实现,程序目录如下: Array shuffle Prime test(trial division) Prime test(Miller-Rabin's method) 2D Array Arbitary Integer Linear congruential generator Maximum subarray problem Bit...
数据结构1.pptx 2X1{SH5V_HSM`5JS[H]Z`JP.png 33XTI0U)]QTVK1MINJY0)F3.png 34MMEH64LMCA}H5G_RXKPGO.png 65]YTLJ{NP7ICB9{]%XK5J2.png 73I2ZJ(3Z5XWL3W1LFVZRCR.png MQJ[~8HPO2L{35`{CY8{WXO.png P)(%S5}WL7HD(09E1...
数据结构与算法复习题 1. 写出以下各词语对应的中文(英) sequential storge structure 顺序存储结构 Abstract Data Type (ADT) 抽象数据类型 二叉排序树 Binary sort tree queue 队列 storge structure 存储结构 ...
数据结构和算法:基本数据结构,排序算法,算法学习工具。基本数据结构,排序算法,算法学习工具
数据结构和算法的学习 学习数据结构和算法的好处 提升编程能力,理解当红技术 区块链的结构就是一个链表(linked list),每一个区块的指针指向前一个区块。 每一个区块内的结构是二叉树(Binary Tree),Merkle ...
lua算法:Lua算法库,涵盖了常用的数据结构和算法
数据结构和算法学习笔记 一、简介 1. 2. 3. 4. 5. 6. 二、数据结构 1. 二维数组(Array2D) 位数组(Bit Set) 静态数组(Fixed Size Array) 有序表(Ordered Array) 2. 队列(Queues) (后进先出) (先进先出)...
排序和数据结构算法 此存储库是一个C#库,具有已实现的排序算法,结构及其算法。 排序算法: 稳定,通用: 不稳定,通用: 非比较算法: -为整数实现 -为整数实现 -为整数实现 -为整数实现 为字符串实现 数据...
数据结构和算法 :fire: 该存储库包含基于数据结构和算法的编码问题的解决方案。 它旨在帮助人们理解 DSA 概念在问题中的应用。 :rocket: :pushpin: 动态规划 :pushpin: 图、DFS 和 BFS :pushpin: 树木 :pushpin: ...
各种数据结构、算法及实用的C#源代码 C#,二叉搜索树(Binary Search Tree)的迭代方法与源代码 二叉搜索树(BST,Binary Search Tree)又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的,可以使用一...
带注释的基本数据结构和算法实现: 二进制位操作: binary_operation.py 二叉树: binary_tree.py 链表: linked_list.py 排序算法: sort.py 搜索算法: search.py 以及其他一些算法实现: 全排列: permuatation....
DSA-Binary-Search-Tree:用于Thinkful的“数据结构和算法”模块的二进制搜索树莳萝
数据结构与算法解决Java和Python中的数据结构和算法问题。问题提出的问题 信息从创建的包中可以看出,程序已根据数据结构进行了划分。 请不要使用archives文件夹添加任何代码。 您还可以添加通过代码实现的某些概念...
《数据结构》 第八次实验报告 "学生姓名 " " "学生班级 " " "学生学号 " " "指导老师 " " 实验内容 1) 有序表的二分查找 建立有序表,然后进行二分查找 2) 二叉排序树的查找 建立二叉排序树,然后查找 需求分析 二分...
C / C ++中的数据结构和算法 该代码由Amit Bansal在学习数据结构和算法时编写。 参考GFG,NPTEL,CLRS。 该存储库包含: 单链表。 添加两个数字表示的链表。 气泡在链接列表中排序合并在链接列表中排序合并排序链表...
数据结构和算法(DSA) 贡献准则 1.文件夹或文件命名 文件夹或文件应满足以下条件: 名称应小写。 该单词应以破折号(-)分隔。 当有新主题时,应创建一个新文件夹并为其建立索引。 一个新文件应该使用添加到索引...
7天入门数据结构与算法 学习目标 形成高效学习方法/习惯 LeetCode 300+的积累 学习方法 切碎知识点(脑图) 刻意练习 反馈(总结/运用) 数据结构 一维数据结构 基础:数组array,链表linked list 高级:栈stack,...
算法和数据结构 目录 └─Outline ├─algorithms │ ├─search │ │ ├─binarysearch │ │ └─linearsearch │ └─sort │ ├─bubblesort │ ├─countingsort │ ├─insertionsort │ ├─...
数据结构数据结构是一种组织数据的方式,以便可以有效地使用它。内容