获取排序数组中在log（n）时间内落在某个范围内的元素数

Question

假设我有一个由以下类组成的数组，按y升序排序：

public class Obj {
    public int x;
    public int y;
}

如何在log（N）time中给定的最小值和最大值范围内找到数组中y值的Obj项目数？

我曾想过使用二进制搜索和减法来查找最小和最大元素的位置，但这不是2 log（n），因为它搜索了两次吗？

public static int getNumberOfItems(Obj[] a, int min, int max) {

Answer 1

这个问题与这里相同，我在这里给出了O（logn）实现。

这个想法是通过范围二分搜索下界和上限。对于您的示例，所有值都在谈论y值。

>

int binarySearchForLeftRange(int a[], int length, int left_range)
{
    if (a[length-1] < left_range)
        return -1;

    int low = 0;
    int high = length-1;

    while (low<=high)
    {
        int mid = low+((high-low)/2);

        if(a[mid] >= left_range)
            high = mid-1;
        else //if(a[mid]<i)
            low = mid+1;
    }

    return high+1;
}

对于上限（右范围），您可以调用以下函数来获取排序数组中值小于或等于它的索引，否则为-1。

int binarySearchForRightRange(int a[], int length, int right_range)
{
    if (a[0] > right_range)
        return -1;

    int low = 0;
    int high = length-1;

    while (low<=high)
    {
        int mid = low+((high-low)/2);

        if(a[mid] > right_range)
            high = mid-1;
        else //if(a[mid]<i)
            low = mid+1;
    }

    return low-1;
}

最后，如果您想得到这个范围内有多少个元素，可以很容易地根据上述两个函数的返回值来确定。

int index_left = binarySearchForLeftRange(a, length, left_range);
int index_right = binarySearchForRightRange(a, length, right_range);

if (index_left==-1 || index_right==-1 || index_left>index_right)
    count = 0;
else
    count = index_right-index_left+1;

测试：（重复）

    int a[] = {1,2,4,4,5,8,12,15,15,23,54};
    int length = sizeof(arr)/sizeof(arr[0]);

    int left_range = 4;
    int right_range = 15;
    int index_left = binarySearchForLeftRange(a, length, left_range); // will be 2
    int index_right = binarySearchForRightRange(a, length, right_range); // will be 8

    int count; // will be 7
    if (index_left==-1 || index_right==-1 || index_left>index_right)
        count = 0;
    else
        count = index_right-index_left+1;

Answer 2

bin search对于这种方法来说很好，O（log N）表示c*log N。所以bin search很好，但您可以通过在范围内搜索omg（minFoundIndex，N）来优化maxIndex searchimg的bin search调用

Answer 3

当您被要求在log（n）时间内做某事时，这通常意味着O（log（n））。

如果这里是这种情况，值得注意的是O（2 log（n））==O（log（n）），即两者是同样的事情。

有关大oh符号的更多背景信息，请参阅维基百科页面。