利用二分搜索算法

Question

我比代码本身更关心思考过程。我应该找到在排序后的数组，使得X < v [I] <ÿ，其中X和ÿ是v [I]部件的数量作为键盘的输入发送。 我应该使用修改后的二进制搜索来有效地解决此问题，而不是通过矢量进行常规搜索。

我的问题是，我不能想象如何在这种情况下实现二进制搜索，该方法似乎不适合我。

有什么想法？

Answer 1

你可以在数组中进行二进制搜索，搜索结果为x和y。然后你可以从y的索引中减去x的索引以获得它们之间有多少物品。

您实际上必须从该结果中减去1，因为您使用的是严格小于。

例如，假设有一个数组：

[3, 6, 8, 10, 14, 39, 41, 100] 

设x = 8和y = 39.

x的索引是2，且y的指数为5。

5-2 = 3

3-1 = 2

如果x和允许是不包含在你的数组中的值，你仍然可以遵循相同的方法。搜索x，如果找不到，请使用刚好大于x的元素索引。对于仅小于y的元素的索引也是如此。

Answer 2

假设原来的阵列V是排序，只要按照这些步骤：

1. 使用二进制搜索来查找值x数组中 - 如果它不存在（在二进制搜索满足的上限和下限），拿到最近的更高价值的指标
2. 执行相同的y值，得到最接近的较低值的指数，如果不是这次
3. 了解有多少项目是在两者之间（除去指数和增加1）

Answer 3

这里如果你有兴趣一大篇：Binary Search

取决于x和y的值，如果他们的上限和下限分别在阵列内的数字，它是作为应用一般的BS一样简单算法，而不是数组的一般第一个和最后一个元素。

把它放在纸上会有帮助。