2

Say I have an array of the following class sorted in ascending order by y:

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

How can I find the number of Obj items in the array that have y values within the min and max range given in log (N) time?

I've thought about using binary search to find the locations of the min and max elements with binarySearch and subtracting, but wouldn't that be 2 log (n) since it's searching twice?

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

3 回答 3

4

当你被要求及时做某事log(n)时，这通常意味着O(log(n))。

如果这里是这样的话，值得注意的是O(2 log(n)) == O(log(n))，即两者是一回事。

有关大哦符号的更多背景信息，请参阅Wikipedia 页面。

于 2013-03-06T09:05:24.807 回答
1

bin 搜索适用于该方法，O(log N) 表示 c * log N。
因此 bin 搜索很好，但您可以通过 searchomg 在范围 (minFoundIndex, N) 内优化 maxIndex searchimg 的 bin 搜索调用。

于 2013-03-06T09:14:57.043 回答
0

这个问题与此处相同，我在此处给出了O(logn)实现。

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

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

    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;
}

  2. 对于上界（右范围），您可以调用以下函数来获取排序数组中值小于或等于它的索引，否则为-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;
}

  3. 最后，如果你想得到这个范围内有多少个元素，根据上面这两个函数的返回值很容易。

    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;
于 2013-12-20T12:52:15.287 回答