- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我不知道术语“惰性”二分搜索是否有效,但我正在浏览一些旧资料,我只是想知道是否有人可以解释惰性二分搜索的算法并将其与非惰性二分搜索算法进行比较-惰性二进制搜索。
比方说,我们有这个数字数组:
2, 11, 13, 21, 44, 50, 69, 88
如何使用 Lazy Binary Search 查找数字 11
?
最佳答案
贾斯汀错了。常见的 binarySearch 算法首先检查目标是否等于当前中间条目,然后再根据需要继续进行左半部分或右半部分。 Lazy binarySearch 算法将相等性检查推迟到最后。
algorithm lazyBinarySearch(array, n, target)
left<-0
right<-n-1
while (left<right) do
mid<-(left+right)/2
if(target>array[mid])then
left<-mid+1
else
right<-mid
endif
endwhile
if(target==array[left])then
display "found at position", left
else
display "not found"
endif
在你的例子中,在一个数组中,
2 11 13 21 44 50 69 88
你想搜索 11
首先我们做一点普通的二分查找,
index 0 1 2 3 4 5 6 7
2 11 13 21 44 50 69 88
left mid right
第一个 while 循环:
left <= right,我们进入第一个while循环。我们通过整数除法 (0+7)/2=3.5=3 计算中间索引,mid = 3。直接我们检查目标 11 是否等于中间索引条目,11 != 21,然后我们决定是向左走还是向右走,我们发现11 < 21,应该向左走。 left index不变,right index变为mid index -1,right = 3 - 1 = 2。完成这一步。
第二个 while 循环:
left <= right, 0 <= 2,我们进入第二个while循环。重新计算 Mid 索引:(0+2)/2=1,mid = 1。立即我们进行相等性检查,目标 11 与索引 1 条目相同,11 == 11。我们找到了这个条目,留下所有左右中间索引(不关心)并打破 while 循环,返回索引 1。
现在我们通过 lazy binazySearch 算法跟踪这个搜索,初始数组的左/右索引设置与之前相同。
第一个 while 循环:
左<右,我们进入第一个while循环。 Mid index 的计算方法与上面相同 = 3。并且比较只检查我们的目标 11 是否大于中间索引条目,将它们是否相等留在 while 循环的最后。 所以我们发现 11 < 21,右索引重置为mid index, right = 3. 完成这一步。
第二个 while 循环:
left < right, 0 < 3,我们进入第二个while循环。 mid 索引通过整数除法重新计算为 mid = (0+3)/2 = 1。 我们再次与中间索引条目 11 进行比较,我们意识到它不大于中间索引条目。我们进入 while 循环的 else 部分,将 right index 重置为 mid index,right = 1。完成这一步。
第三个 while 循环:
left < right, 0 < 1,这一次我们又要重新进入while循环,因为它仍然满足while条件。 mid index变为(0+1)/2=0,mid = 0。比较target 11和mid index entry 2后发现它大于它(11 > 2),left index重置为mid + 1,left = 0 + 1 = 1。完成这一步。
left index = 1 right index = 1,left = right,while循环条件不再满足,无需重新进入。我们进入下面的 if 部分。目标 11 等于左索引条目 11,我们找到目标并返回左索引 1。
如您所见,lazy binarySearch 再执行一个 while 循环步骤,最终实现索引实际上是 1。这就是我在一开始提到的定义中“推迟相等性检查”一词的含义。显然,惰性 binarySearch 算法在到达程序终止之前比普通的 binarySearch 做了更多的事情。 而“惰性”一词体现在何时检查目标等于索引条目的中间值。
然而,lazy binarySearch 在某些其他情况下更可取,但不在这种情况下。
(算法推理部分由本人完成,如需转载请注明出处)
来源:“Data Structures Outside In With Java”,作者:Sesh Venugopal,Prentice Hall
关于binary-search - 什么是惰性二进制搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5958786/
我正在尝试将谷歌地图集成到 Xamarin Android。但是,如标题中所写,收到错误。此错误出现在我的 SetContentView (Resource.Layout.Main); 上,如下所示:
在 Delphi 中如何以非文本模式打开二进制文件?类似于 C 函数 fopen(filename,"rb") 最佳答案 有几个选项。 1。使用文件流 var Stream: TFileStrea
我现在正在处理一个问题,如下所示: 有两个数字 x1 和 x2 并且 x2 > x1。 例如 x1 = 5; x2 = 10; 而且我必须在二进制表示中找到 x1 和 x2 之间的总和。 5 = 10
我有这个“程序集”文件(仅包含 directives ) // declare protected region as somewhere within the stack .equiv prot_s
有没有办法在powershell中确定指定的文件是否包含指定的字节数组(在任何位置)? 就像是: fgrep --binary-files=binary "$data" "$filepath" 当然,
我是一名工程师,而不是软件程序员,所以请原谅我的无知。 我编写了一个 Delphi(7SE) 程序,用于从连接到两个数字温度计的 USB 端口读取“真实”数据类型。 我已经完成了该计划的大部分内容。
我有一些代码,例如: u=(float *)calloc(n, sizeof(float)); for(i=1; i
typedef struct pixel_type { unsigned char r; unsigned char g; unsigned char b;
如何判断二进制数是否为负数? 目前我有下面的代码。它可以很好地转换为二进制文件。转换为十进制时,我需要知道最左边的位是否为 1 以判断它是否为负数,但我似乎无法弄清楚该怎么做。 此外,我如何才能让它返
我有一个带有适当重载的 Vect*float 运算符的 vector 类,我正在尝试创建全局/非成员 float*Vect 运算符,如下所示:(注意这是一个经过大量编辑的示例) class Vect
对于使用 C 编程的项目,我们正在尝试将图像转换为二进制数据,反之亦然。我们在网上找到的所有其他解决方案都是用 C++ 或 Java 编写的。这是我们尝试过的方法: 将图像转换为包含二进制数据的文本文
我需要对列表的元素求和,其中包含所有零或一,如果列表中有 1,则结果为 1,否则为 0。 def binary_search(l, low=0,high=-1): if not l: retu
我到处搜索以找到将 float 转换为八进制或二进制的方法。我知道 float.hex 和 float.fromhex。是否有模块可以对八进制/二进制值执行相同的工作? 例如:我有一个 float 1
当我阅读有关 list.h 文件中的 hlist 的 FreeBSD 源代码时,我对这个宏感到困惑: #define hlist_for_each_entry_safe(tp, p, n, head,
我不知道出了什么问题,也不知道为什么会出现此错误。我四处搜索,但我终究无法弄明白。 void print_arb_base(unsigned int n, unsigned int b) {
在任何语言中都可以轻松地将十进制转换为二进制,反之亦然,但我需要一个稍微复杂一点的函数。 给定一个十进制数和一个二进制位,我需要知道二进制位是开还是关(真或假)。 示例: IsBitTrue(30,1
在下面的代码中,我创建了两个文件,一个是文本格式,另一个是二进制格式。文件的图标显示相同。但是这两个文件的特征完全相同,包括大小、字符集(==二进制)和流(八位字节)。为什么没有文本文件?因为如果我明
我想通读一个二进制文件。谷歌搜索“python binary eof”引导我here . 现在,问题: 为什么容器(SO 答案中的 x)不包含单个(当前)字节而是包含一大堆字节?我做错了什么? 如果应
为什么只允许以 10 为基数使用小数点?为什么以下会引发语法错误? 0b1011101.1101 我输入的数字是否有歧义?除了 93.8125 之外,字符串似乎没有其他可能的数字 同样的问题也适用于其
boost 库中有二进制之类的东西吗?例如我想写: binary a; 我很惭愧地承认我曾尝试找到它(Google、Boost)但没有结果。他们提到了一些关于 binary_int<> 的内容,但我既
我是一名优秀的程序员,十分优秀!