# 查詢值在給定範圍內的數組元素的計數

## 例

```arr[]={2,4,6,8,1,10}
x = 2, y = 8```
`4`

```arr[]={2,4,6,8,1,10}
x = 5, y = 10```
`3`

## 算法

1. 分類 數組。
2. 通過使用二進制搜索找出元素y數組的較大索引，並返回較大索引。
3. 通過使用二進制搜索找出元素x數組的較小索引，並返回較小的索引。
4. 返回較大索引與較小索引之間的差加上1。

## 推薦碼

### C ++代碼查找給定範圍內的數組元素數

```#include<iostream>
#include<algorithm>

using namespace std;

int smallerElement(int arr[], int n, int x)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] >= x)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
int greaterElement(int arr[], int n, int y)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] <= y)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
int countInRange(int arr[], int n, int x, int y)
{
int count = 0;
count = greaterElement(arr, n, y) - smallerElement(arr, n, x) + 1;
return count;
}
int main()
{
int arr[] = {2,4,6,8,1,10 };
int n = sizeof(arr) / sizeof(arr[0]);

sort(arr, arr + n);

int i = 2, j = 8;
cout << countInRange(arr, n, i, j) << endl;

i = 5, j = 10;
cout << countInRange(arr, n, i, j) << endl;
return 0;
}
```
```4
3```

### Java程序查找給定範圍內的數組元素數

```import java.io.*;
import java.util.Arrays;

class NumberOfElements
{
private static int countInRange(int arr[], int n, int x, int y)
{
int count = 0;
count = greaterElement(arr, n, y) -
smallerElement(arr, n, x) + 1;
return count;
}

private static int smallerElement(int arr[], int n, int x)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] >= x)
high = mid - 1;
else
low = mid + 1;
}
return low;
}

private static int greaterElement(int arr[], int n, int y)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] <= y)
low = mid + 1;
else
high = mid - 1;
}
return high;
}

public static void main (String[] args)
{
int arr[] = {2,4,6,8,1,10 };
int n = arr.length;

Arrays.sort(arr);

int x = 2, y = 8;
System.out.println( countInRange(arr, n, x, y)); ;

x = 5;
y = 10;
System.out.println( countInRange(arr, n, x, y));
}
}
```
```4
3```

## 複雜度分析

### 空間複雜度

O（N） 哪裡 “ n” 是數組中元素的數量。 我們考慮的空間是由於對數組進行排序時所佔用的空間。 “在給定範圍內的值的數組元素的計數查詢”問題中未考慮存儲輸入所需的空間。