在阵列二进制搜索包含范围
让我们说,我们已经有序阵列包含这样的元件,在阵列二进制搜索包含范围
[1,2-5,图6,8-9,11-13],2-5是一个代表2,3,4和5的范围,如果我们想要找到“4”,那么索引1(从0开始)就是我们需要的答案。
这是可能的,我们应用二进制搜索像这种类型的元素与constans空间和log(n)时间?
您可以使用二进制搜索,这个概念也可以像魅力范围一样工作。实际上,这是一个通常用于减少时间和空间复杂度的概念,例如在gap encoding
中。 但是,您需要自己编写而不是使用任何库,因为库方法可能不会接受范围。
让我们简单地经过一个二进制搜索的执行上搜索的价值这是在指数的[1, 2-5, 6, 8-9, 11-13]
您给定的输入。
阵列[1, 2-5, 6, 8-9, 11-13]
具有长度,我们决定于它是中间索引。它在那里读取值6
。我们搜索值4
,因此我们继续向左搜索。
我们现在搜索间隔减少到[1, 2-5, 6]
,长度,我们决定中间指数。它读取2-5
。由于4
在该范围内已完成,因此返回索引。
如果例如它会读取5-7
那么我们会继续向左搜索不在5-7
之内。类似地,如果读数为1-3
,我们将继续向右搜索。
下面是一些伪代码的二进制搜索的解释:Binary search algorithm at Wikipedia
如果你有实现的不仅仅是编辑你的问题,告诉我们您已经完成的工作有什么问题,我们会再适应并帮帮我。
谢谢,我遇到了使用范围元素搜索的问题,现在我明白了,只是应用正常的二分查找,但改变了比较方法(搜索号和范围元素),如“ Hao
经过二分法搜索后,您需要比较像2和5这样的结束元素,然后推断在第一部分或第二部分中搜索的位置 – bigbounty
是的。您只需使用自定义比较代码,但它仍然具有相同的复杂性。 – BladeCoder
为什么不先尝试一下,然后在遇到问题时发布代码? – trincot