给定一个已排序的数字数组，如何找到小于 x 的数字的大小

Question

可能的重复：
查找 BST 中所有小于 x 的数字 < /p>

如何我会修改二分搜索来查找排序数组中小于某个数字的数字数量吗？

Answer 1

如果您有一个已经排序的数字数组，只需使用 binary 在排序数组中找到您的项目的插入点搜索算法。插入点的索引为您提供小于目标数量的元素数量。

在您的评论中，您提出了两个很好的问题：

• 如果该号码不在列表中怎么办？

为了处理这个问题，你需要继续搜索，直到找到数字应该存在的点（如果存在的话），即当前元素大于 x 且前一个元素小于 x 的索引。

• 如果有重复怎么办？

为了解决这个问题，不要在第一次找到元素时停止，而是继续搜索，直到下限和上限相遇。如果您达到等于 x 的值，请按照与发现过高数字相同的方式处理它并继续平分。

Answer 2

返回小于二分查找返回值的索引的所有数字。

Answer 3

查找号码并检查索引。

Answer 4

由于这是一个具体的数字数组，而不仅仅是可比较的对象，因此您可能需要查看插值搜索。如果数字均匀分布，则可以在 O(log log n) 时间内找到索引，而不是 O(log n)。

Answer 5

二分查找小于给定数字的最大数字。一旦你有了它的位置，这个位置也直接与你感兴趣的计数相关。

这个伪代码应该让你走上正确的轨道，但我还没有测试它。 k = 给定数字

while left < right
    mid = (left + right) / 2
    if arr[mid] >= k // too big, not interested
        right = mid;
    else             // maybe too small, try bigger values
        left = mid + 1

 right - 1 or left - 1 (they're equal) is the position you're after.

例如：8 11 13 20 50、k = 19

left = 1, right = 5
mid = 3
arr[3] = 13 < 19 => left = 4

left = 4, right = 5
mid = 4
arr[4] = 20 >= 19 => right = 4

left >= right => left - 1 = 4 - 1 = 3 is the position you're after