我有一个数组,其中七个数字从小到大排序。我必须编写一个递归函数来返回特定值的索引。我不允许使用while或for循环。我完全没有办法,也不知道如何解决这个问题。你能给我一些想法吗?
发布于 2018-11-25 07:35:40
由于数组已排序,因此问题可能希望您使用二进制搜索而不是线性搜索方法。查找“递归二进制搜索”。它应该会帮助你解决你的问题。
来自http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html的示例代码
int rBinarySearch(int sortedArray[], int first, int last, int key) {
// function:
// Searches sortedArray[first]..sortedArray[last] for key.
// returns: index of the matching element if it finds key,
// otherwise -(index where it could be inserted)-1.
// parameters:
// sortedArray in array of sorted (ascending) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -insertion_position -1
// if key is not in the array.
if (first <= last) {
int mid = (first + last) / 2; // compute mid point.
if (key == sortedArray[mid])
return mid; // found it.
else if (key < sortedArray[mid])
// Call ourself for the lower part of the array
return rBinarySearch(sortedArray, first, mid-1, key);
else
// Call ourself for the upper part of the array
return rBinarySearch(sortedArray, mid+1, last, key);
}
return -(first + 1); // failed to find key
}发布于 2018-11-26 15:21:40
给定函数签名:
int search(int *sorted, int value, unsigned size)我们首先测试size是否为1,因为这是我们的基本情况。如果size是1,我们检查一个元素sorted[0],看看它是否等于我们正在寻找的value。如果是,则返回return 0,即(唯一)索引。如果没有找到,用return -1表示“找不到”。
如果size大于1,我们将继续。首先,我们计算half,它是size / 2。然后,我们递归地调用自己,并减小大小:
result = search(sorted, value, half);如果此result不是-1,则返回它,因为它是我们想要的索引。如果result为-1,则继续。我们再次递归地调用自己,但这一次使用的是数组的另一半,我们之前没有测试过:
result = search(sorted + half, value, size - half);如果result不是-1,那么我们返回result 加上 half大小。如果result为-1,则简单地return -1,因为该值不在数组中。
https://stackoverflow.com/questions/53463318
复制相似问题