| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2615 人关注过本帖
标题:求助大佬,帮我看下我的递归函数哪里错了
只看楼主 加入收藏
丶随风飘扬
Rank: 2
等 级:论坛游民
帖 子:38
专家分:20
注 册:2019-11-1
结帖率:66.67%
收藏
已结贴  问题点数:20 回复次数:14 
求助大佬,帮我看下我的递归函数哪里错了
题目:在数组中查找元素x并返回其下标,要求从中点开始查找。
程序代码:
int findx3(int a[],int low,int high,int x)
//返回元素X下标,若X不存在,返回-1
//low初始值为下标最小值0,high初始值为下标最大值
{
    int mid;
    if(low>high) return -1;
          mid=(low+high)/2;
    if(a[mid]==x) return mid;
      findx3(a,low,mid-1,x);
      findx3(a,mid+1,high,x);

}
搜索更多相关主题的帖子: 返回 递归 mid 下标 int 
2019-11-04 22:19
zbjzbj
Rank: 12Rank: 12Rank: 12
来 自:郑州
等 级:贵宾
威 望:52
帖 子:633
专家分:3045
注 册:2011-4-22
收藏
得分:10 
这样的查找,费时费力,毫无意义。只有排序的情况下二分法递归查找才有意义
2019-11-05 08:15
丶随风飘扬
Rank: 2
等 级:论坛游民
帖 子:38
专家分:20
注 册:2019-11-1
收藏
得分:0 
老哥,这是老师给我们出的题目,必须这样查找....
2019-11-05 08:24
丶随风飘扬
Rank: 2
等 级:论坛游民
帖 子:38
专家分:20
注 册:2019-11-1
收藏
得分:0 
回复 2楼 zbjzbj
那我们老师应该是没说清楚前提,否则这样根本实现不了
2019-11-05 08:41
zbjzbj
Rank: 12Rank: 12Rank: 12
来 自:郑州
等 级:贵宾
威 望:52
帖 子:633
专家分:3045
注 册:2011-4-22
收藏
得分:0 
老弟呀,你就不能先排一下序
2019-11-05 08:58
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:10 
返回下标真不优美,因为下标是相对位置,本身并不独立

程序代码:
#include <stdio.h>

int* binary_search( const int a[], size_t n, int key )
{
    if( n == 0 )
        return NULL;
    if( key < a[n/2] )
        return binary_search( a, n/2, key );
    if( a[n/2] < key  )
        return binary_search( a+n/2+1, n-n/2-1, key );
    return (int*)&a[n/2];
}

size_t findx3( const int a[], size_t n, int key )
{
    int* p = binary_search( a, n, key );
    if( p )
        return p-a;
    return -1;
}

#include <assert.h>

int main( void )
{
    int a[9];
    for( size_t i=0; i!=sizeof(a)/sizeof(*a); ++i )
        a[i] = i;

    for( size_t i=0; i!=sizeof(a)/sizeof(*a); ++i )
    {
        size_t index = findx3( a, sizeof(a)/sizeof(*a), a[i] );
        assert( index == i );
    }
}

2019-11-05 09:03
丶随风飘扬
Rank: 2
等 级:论坛游民
帖 子:38
专家分:20
注 册:2019-11-1
收藏
得分:0 
回复 5楼 zbjzbj
我们老师是直接让我在数组里这样找啊....没说要先排序
2019-11-05 11:42
丶随风飘扬
Rank: 2
等 级:论坛游民
帖 子:38
专家分:20
注 册:2019-11-1
收藏
得分:0 
回复 5楼 zbjzbj
我懂你什么意思了,不是我死脑筋啊,我们老师的意思就是让我们在一个无序数组里找,不能先排序。
2019-11-05 12:07
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
以下是引用丶随风飘扬在2019-11-5 12:07:14的发言:

在一个无序数组里找,不能先排序。
无序数组是没法进行二分查找的。
或者说,一定要二分查找的话,效率会比顺序操作低很多。因为涉及到 内存页面调度,控制流程的分支预测 等。

无序二分查找( 首元素指针,长度,需要查找的数 )
{
    if( 中间元素值 == 需要查找的数 )
        返回中间元素的下标;

    size_t index = 无序二分查找( 首元素指针,长度/2,需要查找的数 )
    if( index != -1 )
        return index;

    return 无序二分查找( 首元素指针+长度/2+1,长度-长度/2-1,需要查找的数 )
}
2019-11-05 13:26
丶随风飘扬
Rank: 2
等 级:论坛游民
帖 子:38
专家分:20
注 册:2019-11-1
收藏
得分:0 
回复 6楼 rjsp
大佬,你的第二个函数会报错。
图片附件: 游客没有浏览图片的权限,请 登录注册

E:\C_program\递归调用\main.c|173|error: conflicting types for 'findx3'|
2019-11-05 14:38
快速回复:求助大佬,帮我看下我的递归函数哪里错了
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.063219 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved