求助大佬，帮我看下我的递归函数哪里错了 - 编程论坛

#2

zbjzbj2019-11-05 08:15

这样的查找，费时费力，毫无意义。只有排序的情况下二分法递归查找才有意义

#3

丶随风飘扬2019-11-05 08:24

老哥，这是老师给我们出的题目，必须这样查找....

#4

丶随风飘扬2019-11-05 08:41

回复 2楼 zbjzbj

那我们老师应该是没说清楚前提，否则这样根本实现不了

#5

zbjzbj2019-11-05 08:58

老弟呀，你就不能先排一下序

#6

rjsp2019-11-05 09:03

返回下标真不优美，因为下标是相对位置，本身并不独立

程序代码：

#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 );
    }
}

#7

丶随风飘扬2019-11-05 11:42

回复 5楼 zbjzbj

我们老师是直接让我在数组里这样找啊....没说要先排序

#8

丶随风飘扬2019-11-05 12:07

回复 5楼 zbjzbj

我懂你什么意思了，不是我死脑筋啊，我们老师的意思就是让我们在一个无序数组里找，不能先排序。

#9

rjsp2019-11-05 13:26

以下是引用丶随风飘扬在2019-11-5 12:07:14的发言：

在一个无序数组里找，不能先排序。

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

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

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

    return 无序二分查找( 首元素指针+长度/2+1，长度-长度/2-1，需要查找的数 )
}

#10

丶随风飘扬2019-11-05 14:38

回复 6楼 rjsp

大佬，你的第二个函数会报错。

只有本站会员才能查看附件，请登录

E:\C_program\递归调用\main.c|173|error: conflicting types for 'findx3'|

#11

丶随风飘扬2019-11-05 15:01

回复 9楼 rjsp

大佬，你程序的思路应该是先对中点进行判断，若不是要找的数，再对左半部分进行查找，再找不到，最后对右半部进行查找。
可是如果没有要找的那个数的话，你程序里并没有对这个情况进行判断并返回-1。
还有index什么时候会等于-1？毕竟你函数里并没有return -1呀。

#12

丶随风飘扬2019-11-05 15:14

回复 9楼 rjsp

这是我根据你的提示写的代码，我自己试了一下，设了数组a有五个数1 5 6 9 3。要查找9的下标，当9的下标是0,1,2的时候就能找到，9的下标是4,5的时候就找不到，也不会返回-1.

程序代码：

int findx4(int a[],int n,int x)
{
    if(a[n/2]==x)
        return n/2;
    size_t index = findx4(a,n/2,x);
    if(index!=-1)
        return index;
    return findx4(a+n/2+1,n-n/2-1,x);
}

#13

rjsp2019-11-05 15:18

回复 10楼丶随风飘扬

你要将源码贴全
conflicting types for 'findx3' 的意思是你在其它地方声明了一个同名的函数 findx3，但函数原型却不一样。

#14

rjsp2019-11-05 15:22

回复 11楼丶随风飘扬

只是一个简单的为代码而已，一开始的 if( 数组长度 == 0 ) return -1; 省略了

#15

rjsp2019-11-05 15:27

回复 12楼丶随风飘扬

应该这么改，虽然挺丑的

程序代码：

size_t findx4( const int a[], size_t n, int key )
{
    if( n == 0 )
        return -1;

    if( key < a[n/2] )
        return findx4( a, n/2, key );

    if( a[n/2] < key  )
    {
        size_t index = findx4( a+n/2+1, n-n/2-1, key );
        if( index != -1 )
            index += n/2+1;
        return index;
    }

    return n/2;
}