C#实现的Jump Search算法是否正确？如何优化提升效率？

原代码存在的问题 #

• 变量名不一致：定义了arr_size存储数组长度，但后续多处使用未定义的array_size，会直接导致编译错误。
• 数组越界风险：当数组长度为1时，step = (int)Math.Sqrt(arr_size)结果为1，此时访问arr[step]会超出数组索引范围（数组索引最大为0）。
• 循环条件逻辑缺陷：while循环的step < array_size-1限制会导致当step等于数组最后一个索引时，循环直接终止，无法处理该位置元素小于等于目标值的情况。

修正后的正确实现 #

public int JumpSearch(int[] arr, int key)
{
    int arrSize = arr.Length;
    if (arrSize == 0)
        return -1; // 处理空数组边界情况

    int stepSize = (int)Math.Sqrt(arrSize);
    int step = stepSize;
    int prev = 0;

    // 找到目标值所在的块
    while (step < arrSize && arr[step] <= key)
    {
        prev = step;
        step += stepSize;
    }

    // 在目标块内进行线性搜索，确保边界不超过数组末尾
    int end = Math.Min(step, arrSize - 1);
    for (int j = prev; j <= end; j++)
    {
        if (arr[j] == key)
            return j;
    }

    return -1;
}

效率提升与改进建议 #

• 避免重复计算步长：原代码每次循环都重新计算平方根，提前将步长值存储为变量，减少重复计算的开销。
• 提前过滤无效情况：如果目标值小于数组第一个元素、大于最后一个元素，直接返回-1，跳过后续循环操作。
• 优化平方根计算：在.NET Core 3.0及以上版本中，使用BitOperations.Sqrt((uint)arrSize)替代Math.Sqrt，获得更高效的整数平方根计算结果，避免浮点数转换的精度问题。
• 明确输入约束：Jump Search仅适用于升序排列的有序数组，建议在方法开头添加注释或断言，明确输入要求，避免误用。

内容的提问来源于stack exchange，提问作者90CK