C语言实现Jump Search算法的两处技术疑问

你的实现代码 #

#include "search_algos.h"

/**
 * jump_search - search for a value in an array using the
 * jump search algorithm
 * @array: the array to be searched
 * @size: size of the array to be searched
 * @value: value to be searched in the array
 *
 * Return: If the value is found in the array, it will return
 * the index of the first match it has found. Otherwise, it
 * returns -1, and errno is set appropriately.
 */
int jump_search(int *array, size_t size, int value)
{
        int val = sqrt(size), prev, step;

        if (!array)
                return (-1);

        prev = 0;
        step = val;
        while (step < (int)size && array[step] < value)
        {
                prev = step;
                step += val;
        }
        while (prev <= step && prev < (int)size)
        {
                if (array[prev] == value)
                        return prev;
                prev += 1;
        }
        return -1; 
}

疑问解答 #

疑问1：使用sqrt()不向下取整会不会导致访问非法内存？ #

不会，原因有两点：

• 当把sqrt()返回的double值赋值给int变量时，C语言会自动截断小数部分，等价于向下取整。比如sqrt(5)返回约2.236，赋值给int后会变成2，相当于已经完成了向下取整操作。
• 第一个循环里有step < (int)size的判断，只有step在数组合法索引范围内时，才会访问array[step]。即使step累加后超过数组长度，循环会直接终止，不会执行越界的内存访问。比如数组长度为5，step最终变成6时，6 < 5不成立，循环停止，不会访问array[6]。

疑问2：实现逻辑导致结果不一致的原因 #

你的核心逻辑没问题，但两个细节可能引发结果异常：

1. 第二个循环范围冗余：当step超过数组长度时，prev <= step的条件会让循环尝试走到step的位置，虽然prev < (int)size的限制会阻止越界，但容易让你误以为搜索范围错误。正确的搜索范围应该是[prev, min(step, size-1)]，可以把第二个循环条件简化为prev < (step < (int)size ? step : (int)size)，逻辑更清晰。
2. size_t转int的溢出风险：如果数组长度size超过int的最大值，(int)size会变成负数，导致循环条件判断错误。如果要处理超大数组，建议把prev和step定义为size_t类型，避免类型转换的问题。

另外，虽然你的代码能正确找到目标值，但如果测试用例期望直接匹配array[step]的位置而非从prev遍历到step，可能会误以为结果不一致，但实际上算法要求返回第一个匹配的索引，你的逻辑是符合要求的。

内容的提问来源于stack exchange，提问作者Leuel Asfaw