拉格朗日插值查找的疑问

最近学到拉格朗日插值查找,发现了一个bug

网上找到的写法大多是这样

void lagrangeSearch(int num, int *a, int length)
{
    int count = 0; //记录查找几次,对比二分查找
    int flag = 0; //标志是否找到
    int max = length - 1;
    int min = 0;
    //int mid =  (max+min)/2 //容易溢出
    int mid;


    while (min <= max)
    {
        count++;
        //没有判断num-a[min]是否小于0,如果小于0不就出错了吗,mid有可能变成负数,造成不正确的访问
        mid = min + (max - min) * 1.0 *(num - a[min]) / (a[max] - a[min]);
        if (num > a[mid])
        {
            min = mid + 1;
        }
        else if (num < a[mid])
        {
            max = mid - 1;
        }
        else
        {
            flag = 1;
            break;
        }
    }

    if (flag == 1)
    {
        printf("拉格朗日找到了,下标为:%d,查找了%d次\n", mid, count);
    }
    else {
        printf("不存在\n");
    }
}

如代码所示(mid = min + (max - min) * 1.0 *(num - a[min]) / (a[max] - a[min]);)

如果不加以判断的话,num-a[min]是有可能小于0的,造成整个式子小于0,mid就变成了负数,如此访问的话不就访问到了错误的地址吗?

请问我考虑的对吗?

自己改动后的:

//拉格朗日查找
void lagrangeSearch(int num, int *a, int length)
{
    int count = 0; //记录查找几次,对比二分查找
    int flag = 0; //标志是否找到
    int max = length - 1;
    int min = 0;
    //int mid =  (max+min)/2 //容易溢出
    int mid;

    //当num<a[min]时,拉格朗日差值为负,无法正常判断
    if (num >= a[min] && num <= a[max])
    {
        while (min <= max)
        {
            count++;
            mid = min + (max - min) * 1.0 *(num - a[min]) / (a[max] - a[min]);
            if (num > a[mid])
            {
                min = mid + 1;
            }
            else if (num < a[mid])
            {
                max = mid - 1;
            }
            else
            {
                flag = 1;
                break;
            }
        }
    }


    if (flag == 1)
    {
        printf("拉格朗日找到了,下标为:%d,查找了%d次\n", mid,count);
    }
    else {
        printf("不存在\n");
    }
}

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问