为什么我的代码会超时？

a905448839

二分查找

本题要求实现二分查找算法。

函数接口定义：

Position BinarySearch( List L, ElementType X );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

裁判测试程序样例：

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

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    Position P;

    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d\n", P);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1：
5
12 31 55 89 101
31
输出样例1：
2

输入样例2：
3
26 78 233
31
输出样例2：
0


我的代码：

Position BinarySearch( List L, ElementType X )
{
        Position right = L->Last,left = 1;
    Position z = (right+left)/2;
        while(1)
        {
        if(X > L->Data[z])
        {
            left = z;
            z = (right+left+1)/2;
        }
        else if(X < L->Data[z])
        {
            right = z;
             z = (right+left)/2;
        }
        else
            return z;
        if(right == left)
        return 0;
    }
    
}

结果部分超时：


求高手给出超时原因！十分感谢！

isdkz

你的代码可能会陷入无限循环，导致超时。问题在于你的“while”循环的终止条件不够完备。你的代码是这样设定的：只有当 right == left 时才会结束循环。然而在一些情况下， right 和 left 可能永远不会相等，特别是在你寻找的元素 X 不存在于列表 L 时。

为了修复这个问题，你可以将终止条件改为 right < left ，这样当 right 和 left 相交时，循环就会结束。这种情况下，你就知道 X 并不存在于列表 L 中。同时注意更新 right 和 left 的方式，保证在每次循环中 right 和 left 一定会向中间靠拢。所以如果 X 大于 L->Data[z] ， left 应该设置为 z+1 ，而不是 z 。同样，如果 X 小于 L->Data[z] ， right 应该设置为 z-1 ，而不是 z 。

下面是修复后的代码：

Position BinarySearch( List L, ElementType X )
{
    Position right = L->Last, left = 1;
    while (left <= right)
    {
        Position mid = (right + left) / 2;
        if (X > L->Data[mid])
            left = mid + 1;
        else if (X < L->Data[mid])
            right = mid - 1;
        else
            return mid;
    }
    return NotFound;  // 注意这里返回你定义的NotFound，也就是0
}

这个修复的版本应该可以解决你的超时问题。

陶远航

可能的超时原因是您的循环没有结束条件。请检查是否有以下情况：

如果X不存在于L->Data，请确保程序可以找到搜索失败。当left和right缩小仅剩一个值，但还未找到X时，应该返回NotFound。

如果while循环的结束条件缺失或不正确，这也可能导致超时。建议在while循环中添加left和right的边界检查。

下面是改进后的代码：

Position BinarySearch( List L, ElementType X )
{
    Position right = L->Last, left = 1;
    while (left <= right)
    {
        Position mid = (right + left) / 2;
        if (X > L->Data[mid])
            left = mid + 1;
        else if (X < L->Data[mid])
            right = mid - 1;
        else
            return mid;
    }
    return NotFound;  // 注意这里返回你定义的NotFound，也就是0
}

a905448839

陶远航 发表于 2023-6-4 20:38
可能的超时原因是您的循环没有结束条件。请检查是否有以下情况：

如果X不存在于L->Data，请确保程序可以 ...

两位大佬的问题的确能够解决这个题，但是思路和我的有出入。我是想一直用二分法找出中间点那个是不是要找的值。如果不是一直找到左边的点和右边的点相等的情况下返回NotFound。我的原始代码基础上有什么改进的办法没有呢？

a905448839

isdkz 发表于 2023-6-4 20:37
你的代码可能会陷入无限循环，导致超时。问题在于你的“while”循环的终止条件不够完备。你的代码是这样设 ...

两位大佬的问题的确能够解决这个题，但是思路和我的有出入。我是想一直用二分法找出中间点那个是不是要找的值。如果不是一直找到左边的点和右边的点相等的情况下返回NotFound。我的原始代码基础上有什么改进的办法没有呢？