假设我们想用 C 语言编写一个函数,在未排序的整数数组中找到指定的目标值。一般来说,这很简单并且在 O(n) 时间内运行:
int search(int *data, int len, int target)
{
int i;
for(i = 0; i < len; i++)
if(data[i]==target) return i;
return -1;
}
假设我们是自虐狂,想用分而治之的算法来解决这个问题。我们会在递归部分遇到麻烦,因为我们不能每次都排除一半数组,就像我们使用二分查找一样:
int search(int *data, int start, int stop, int target)
{
// Base case: we've divided the array into two size subarray
if(stop==start+1)
{
if(data[start]==target) return start;
if(data[stop]==target) return stop;
return -1;
}
/* The recursion part is tricky.
We *need* to parse both halves of the array, because we can't safely
exclude any part of the array; it's not sorted, so we can't predict
which half it's going to be in.*/
else
{
/** This obviously doesn't work. */
int mid = (stop-start)/2;
return search(data, start, mid, target);
return search(data, mid+1, stop, target);
}
}
有什么办法可以使这项工作?
注意:这并不是要求人们为我做作业,正如你们中的一些人在阅读这个问题时可能会想的那样。然而,我在尝试解决本周早些时候提交的作业中的一个问题时遇到了这个问题,这激发了我的好奇心。