获取日志落入一定范围内，在排序后的数组元素的数目（n）的时间 [英] Get number of elements in a sorted array that fall within a certain range in log(n) time

问题描述

说我有下面的类按升序排序由y的数组：

 公共类的OBJ {
    公众诠释X;
    公众诠释Ÿ;
}
 

我如何找到数组中的OBJ项目有最小和日志（N）的时间给予最大范围内的y值多少？

我已经想过使用二进制搜索来找到最小的带的binarySearch和减法的位置和最大的元素，但是那不是2的log（n），因为它的搜索两次？

 公共静态INT getNumberOfItems（的OBJ []一，诠释分钟，INT最大）{
 

解决方案

当你被要求做一些在的log（n）时，这通常意味着 O（日志（N））。

如果这是这里的情况，值得一提的是， 0（2的log（n））== O（日志（N）），即两者是同样的事情。

有关进一步的背景大哦符号，请参见维基百科页面。

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) {

解决方案

When you're asked to do something in log(n) time, this usually means O(log(n)).

If that's the case here, it is worth noting that O(2 log(n)) == O(log(n)), i.e. the two are the same thing.

For further background on the big-oh notation, see the Wikipedia page.

这篇关于获取日志落入一定范围内，在排序后的数组元素的数目（n）的时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！