在阵列二进制搜​​索包含范围

Question

让我们说，我们已经有序阵列包含这样的元件，

[1，2-5，图6，8-9，11-13]，2-5是一个代表2,3,4和5的范围，如果我们想要找到“4”，那么索引1（从0开始）就是我们需要的答案。

这是可能的，我们应用二进制搜索像这种类型的元素与constans空间和log（n）时间？

Answer 1

您可以使用二进制搜索，这个概念也可以像魅力范围一样工作。实际上，这是一个通常用于减少时间和空间复杂度的概念，例如在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

如果你有实现的不仅仅是编辑你的问题，告诉我们您已经完成的工作有什么问题，我们会再适应并帮帮我。