c - 利用二分查找算法

Question

与代码本身相比，我对思维过程更感兴趣。我应该找到排序数组中 v[i] 组件的数量，这样 x < v[i] < y，其中 x 和 y 作为键盘输入发送。我应该使用修改后的二进制搜索而不是通过 vector 进行常规搜索来有效地解决这个问题。

我的问题是我无法想象在这种情况下如何实现二分查找，这个方法似乎不适合我。

有什么想法吗？

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 和 y 是数组中不包含的值，您仍然可以采用相同的方法。搜索 x，如果没有找到，则使用刚好大于 x 的元素的索引。对于小于 y 的元素的索引也是如此。