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

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

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

如何在log（N）时间内找到y值在最小值和最大值范围内的数组中Obj项的数量？

我已经考虑过使用二进制搜索来找到带有binarySearch和减法的min和max元素的位置，但是因为它搜索了两次所以不会是2 log（n）吗？

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

Answer 1

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

如果是这种情况，值得注意的是O(2 log(n)) == O(log(n)) ，即两者是相同的。

有关big-oh表示法的更多背景信息，请参阅Wikipedia页面 。

Answer 2

bin搜索适用于该方法，O（log N）表示c * log N.
所以bin搜索很好，但你可以通过范围内的searchomg（minFoundIndex，N）优化bin搜索调用maxIndex searchimg。

Answer 3

这个问题与此相同，我给出了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] 

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] 

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;