首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在排序数组中查找元素,不使用for或while

问在排序数组中查找元素,不使用for或while
EN

Stack Overflow用户
提问于 2018-11-25 07:30:57
回答 2查看 220关注 0票数 0

我有一个数组,其中七个数字从小到大排序。我必须编写一个递归函数来返回特定值的索引。我不允许使用while或for循环。我完全没有办法,也不知道如何解决这个问题。你能给我一些想法吗?

EN

回答 2

Stack Overflow用户

发布于 2018-11-25 07:35:40

由于数组已排序,因此问题可能希望您使用二进制搜索而不是线性搜索方法。查找“递归二进制搜索”。它应该会帮助你解决你的问题。

来自http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html的示例代码

代码语言:javascript
复制
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
}
票数 1
EN

Stack Overflow用户

发布于 2018-11-26 15:21:40

给定函数签名:

代码语言:javascript
复制
int search(int *sorted, int value, unsigned size)

我们首先测试size是否为1,因为这是我们的基本情况。如果size是1,我们检查一个元素sorted[0],看看它是否等于我们正在寻找的value。如果是,则返回return 0,即(唯一)索引。如果没有找到,用return -1表示“找不到”。

如果size大于1,我们将继续。首先,我们计算half,它是size / 2。然后,我们递归地调用自己,并减小大小:

代码语言:javascript
复制
result = search(sorted, value, half);

如果此result不是-1,则返回它,因为它是我们想要的索引。如果result为-1,则继续。我们再次递归地调用自己,但这一次使用的是数组的另一半,我们之前没有测试过:

代码语言:javascript
复制
result = search(sorted + half, value, size - half);

如果result不是-1,那么我们返回result 加上 half大小。如果result为-1,则简单地return -1,因为该值不在数组中。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/53463318

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档