2

可能重复:
在 BST 中找到所有小于 x 的数字

如何修改二进制搜索以查找排序数组中小于某个数字的数字数量?

4

5 回答 5

2

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

于 2010-06-27T21:36:06.297 回答
2

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

在您的评论中,您提出了两个很好的问题:

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

为了处理这个问题,你一直在寻找,直到找到数字应该存在的点,即当前元素大于 x 且前一个元素小于 x 的索引。

  • 如果有重复怎么办?

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

于 2010-06-27T20:26:52.947 回答
0

查找号码并检查索引。

于 2010-06-27T23:15:08.470 回答
0

由于这是专门的数字数组,而不仅仅是可比较的对象,您可能需要查看插值搜索。如果数字是均匀分布的,它可以在 O(log log n) 时间内找到索引,而不是 O(log n)。

于 2010-06-27T23:48:02.220 回答
-1

对小于给定数字的最大数字进行二进制搜索。一旦你有了它的位置,那个位置也与你感兴趣的计数直接相关。

这个伪代码应该能让你走上正轨,但我还没有测试过。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
于 2010-06-27T20:53:42.153 回答