在 C# 中，数组范围查找算法是指在给定范围内搜索特定值或满足某种条件的值。这些算法通常通过遍历、二分查找、或自定义逻辑实现。以下将详细介绍常见的范围查找算法及其时间和空间复杂度。

1. 线性查找（Linear Search）

实现原理

逐个遍历数组中的元素，并检查该元素是否在指定范围内。找到匹配项后，可以执行返回或继续搜索。

时间和空间复杂度

• 时间复杂度：O(n)，需要检查所有元素。
• 空间复杂度：O(1)，无需额外存储。

示例代码

int[] array = { 1, 5, 8, 12, 15, 20 };
int lowerBound = 10, upperBound = 15;

var results = array.Where(x => x >= lowerBound && x <= upperBound).ToList();
Console.WriteLine(string.Join(", ", results)); // 输出: 12, 15

2. 二分查找（Binary Search）

实现原理

二分查找算法适用于有序数组。在范围查找中，可以通过找到范围边界的起始点和结束点来确定结果。

时间和空间复杂度

• 时间复杂度：O(log n)，每次将搜索范围减半。
• 空间复杂度：O(1)，无需额外存储。

示例代码

int[] sortedArray = { 1, 5, 8, 12, 15, 20 };
int lowerBound = 10, upperBound = 15;

int startIndex = Array.BinarySearch(sortedArray, lowerBound);
int endIndex = Array.BinarySearch(sortedArray, upperBound);

// 修正索引位置
startIndex = startIndex < 0 ? ~startIndex : startIndex;
endIndex = endIndex < 0 ? ~endIndex - 1 : endIndex;

for (int i = startIndex; i <= endIndex; i++)
{
    Console.WriteLine(sortedArray[i]); // 输出: 12, 15
}

3. 滑动窗口法（Sliding Window）

实现原理

滑动窗口法用于高效地在指定范围内查找连续元素。窗口的左右边界根据范围条件动态调整。

时间和空间复杂度

• 时间复杂度：O(n)，每个元素最多被访问两次（左指针和右指针移动）。
• 空间复杂度：O(1)，无需额外存储。

示例代码

int[] array = { 1, 5, 8, 12, 15, 20, 25, 30 };
int lowerBound = 10, upperBound = 20;

int left = 0, right = 0;
while (right < array.Length)
{
    if (array[right] >= lowerBound && array[right] <= upperBound)
    {
        Console.WriteLine(array[right]); // 输出: 12, 15, 20
    }
    right++;
}

4. 索引范围查找（Range Queries）

实现原理

构建辅助数据结构（如前缀和、区间树或跳跃表）以快速定位指定范围内的值。适合需要多次查找的场景。

时间和空间复杂度

• 时间复杂度：构建阶段：O(n)（前缀和）或 O(n log n)（区间树）。查找阶段：O(1)（前缀和）或 O(log n)（区间树）。
• 空间复杂度：O(n)，用于存储辅助数据。

示例代码（前缀和）

int[] array = { 1, 5, 8, 12, 15, 20 };
int lowerBound = 10, upperBound = 20;

int[] prefixSum = new int[array.Length + 1];
for (int i = 0; i < array.Length; i++)
{
    prefixSum[i + 1] = prefixSum[i] + (array[i] >= lowerBound && array[i] <= upperBound ? 1 : 0);
}

// 范围查询：前缀和快速定位范围内的值
int resultCount = prefixSum[array.Length] - prefixSum[0];
Console.WriteLine($"范围内的元素数量: {resultCount}");

5. 使用 LINQ 查询

实现原理

LINQ 提供了一种简洁的方式进行范围过滤和查找，可以结合 Where、Take 和 Skip 等方法实现。

时间和空间复杂度

• 时间复杂度：O(n)，取决于源数据和过滤条件的复杂性。
• 空间复杂度：O(k)，其中 k 是结果集中匹配的元素数量。

示例代码

int[] array = { 1, 5, 8, 12, 15, 20 };
int lowerBound = 10, upperBound = 15;

var rangeResults = array.Where(x => x >= lowerBound && x <= upperBound).ToArray();
Console.WriteLine(string.Join(", ", rangeResults)); // 输出: 12, 15

不同算法的适用场景对比

总结

在 C# 中选择数组范围查找算法时，需要综合考虑数据规模、查找条件、查询频率以及性能要求：

• 数据量小：使用线性查找或 LINQ 查询。
• 有序数据：优先使用二分查找。
• 多次查询：选择索引范围查找方法。
• 连续条件：适用滑动窗口法。