英文:
Jump Search Algorithm in C
问题
I am trying to implement the jump search algorithm, and I had a couple of questions. Here is my attempt of the algorithm:
#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;
}
I have seen implementations of the algorithm in the internet and I have seen that they use the sqrt() function which is alright, but they don't floor it and just go on with the implementation but won't that be accessing an illegal memory location?
My second question is that I have implemented the algorithm in a way that once I have found an element greater than value to be searched, I go back to the previous block and do a linear search in that block. But it is giving me some inconsistent results.
英文:
I am trying to implement the jump search algorithm, and I had a couple of questions. Here is my attempt of the algorithm:
#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;
}
I have seen implementations of the algorithm in the internet and I have seen that they use the sqrt() function which is alright, but they don't floor it and just go on with the implementation but wont that be accessing an illegal memory location?
My second question is that I have implemented it the algorithm in a way that once I have found an element greater than value to be searched I go back to the previous block and do a linear search in that block. But it is giving me some inconsistent results.
答案1
得分: 1
以下是已翻译的部分：
对于你的第一个问题，即使平方根的值不是完美的且平方根的值不是整数，算法仍然能正常工作，但在步骤增量中，步骤值可能超过数组的大小，可能会错过数组的最后元素，但除此之外，算法始终能正常工作。
至于回答你的第二个问题，跳跃搜索算法有其优点和缺点，如果你追求算法的轻微加速和更容易的实现，你将不得不处理其内存安全性问题，因此可能需要进行额外的比较，这会减慢程序的运行速度。因此，如果你迫切需要速度和性能，我建议选择二分搜索算法。
英文:
For your first question, even if the square root value is not perfect and the value of the square root is not an integer, then also the algorithm will work correctly, but in the step increments the step value may go above the size of the array and it may miss the last elements of the array, but other than that the algorithm will always work.
And to answer your second question, the jump search algorithm has its pros and cons, and if you are going for the little extra speed of the algorithm and its easier implementation, you will have to deal with its memory safety issues, and due to this, you may have to do extra comparisons and this will slow down the program. Hence, if you need the speed and performance so badly, I would suggest going for the Binary Search algorithm.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论