C家庭作业帮助:通过数组搜索

Question

我正在研究一个问题,我给出了一个排序的整数数组,我应该从用户那里获取一个输入,搜索输入,并返回该输入的第一个实例(如果它存在)和它出现的次数.

我用以下方法编写了一个程序:我从用户那里得到了一个输入.然后我使用二进制搜索来查找值.如果它存在,那么我将索引存储为m.之后,我写了两个while循环.第一个循环检查左边的值的出现次数,第二个循环检查相同,但是向右.例如,二进制搜索可能正在寻找5,并且它找到它.然而,它落在第三个,即.{.....5,5,**5**,5....}.第一个while循环将计算左边的两个循环,而第二个循环将计算右边的一个循环.然后我将它们全部加起来并返回实例总数.如果输入值不存在,那么我跳过上述代码并简单地返回-1.

在main函数体中,我然后检查返回值.如果是-1,我告诉用户该值尚未找到.如果返回值> = 0,则打印所需信息.

无论如何,我已经为程序编写了C代码,但我无法使其正常工作.我得到一个段.错误错误,我不知道我做错了什么.无论如何,任何帮助将不胜感激.我一直在为这个问题敲打头脑.这很有趣也很难,我认为我有正确的逻辑; 但我不能让它正常工作.无论如何,这里是代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

/* function prototype */

int get_num_of_ints( const int* arr, size_t r, int N, size_t* f, size_t* count );

int main()
{   
    int i;
    int N;                                      /* input variable */
    int arr[]={1,1,2,3,4,4,4,4,5,5,6,7,7,7,7,8,9,9};                    /* array of sorted integers */
    size_t r = sizeof(arr[i])/sizeof(int);                      /* right bound */
    size_t f;                                       /* first match index */
    size_t *fPtr;
    fPtr = &f;
    size_t count;                                       /* total number of matches */
    size_t *countPtr;                                   
    countPtr = &count;  

    printf( "\nPlease input the integer you would like to find.\n" );
    scanf( "%d", &N );

    int a = get_num_of_ints( arr, r, N, fPtr, countPtr );

    if( a == -1)    
    printf( "%d has not been found.\n", N );

    else if(a >= 0){
    printf( "The first index is %d.\n", f );
    printf( "The total number of values is %d.\n", count );
    }

    return 0;
}

/* function definition */

int get_num_of_ints( const int* arr, size_t r, int N, size_t* f, size_t* count )
{
    int l = 0;
    int m;
    int w=r;
    size_t *fPtr;
    size_t *countPtr;


    while(l <= r){
        m = l +(r - l)/2;
        if(arr[m] < N)
            l = m+1;
        else if(arr[m] > N)
            r = m-1;
        else if(arr[m]==N)
            m=m;
            break;
    }
    if( l > r)
        m = -1;

    if( m >= 0 ){   

        int j = m-1;
        int L = 0;

        while(arr[j] == arr[m] && j >= 0){
            L++;
            j--;
        }


        if( j>= 0 && L > 0 )
            *fPtr=j;
        else
            *fPtr=m;

        int h = m + 1;
        int R = 0;

        while( arr[h]==arr[m] && h <= w ){
            R++;
            h++;
        }

        *countPtr = (R + L + 1);
        return *fPtr;
    }

    else if( m==-1)
        return -1;
}   

Answer 1

while(arr[j] == arr[m] && j >= 0)

您应该在这里切换这两个条件的顺序,否则您将尝试阅读arr[-1].第二个while循环也是如此.

另一个问题是r应该从比数组大小小1开始,因为它arr[array_size]已经过了结束.

编辑:

一个严重的问题是你正在写未初始化的指针countPtr,fPtr当你应该写*count和*f.这可能是导致段错误的原因.这很容易在调试器中发现.