a905448839 发表于 2023-6-4 20:35:32

为什么我的代码会超时?

二分查找

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

函数接口定义:

Position BinarySearch( List L, ElementType X );

其中List结构定义如下:

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data;
    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;
    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)
      {
            left = z;
            z = (right+left+1)/2;
      }
      else if(X < L->Data)
      {
            right = z;
             z = (right+left)/2;
      }
      else
            return z;
      if(right == left)
      return 0;
    }
   
}


结果部分超时:


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

isdkz 发表于 2023-6-4 20:37:22

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

为了修复这个问题,你可以将终止条件改为 right < left ,这样当 right 和 left 相交时,循环就会结束。这种情况下,你就知道 X 并不存在于列表 L 中。同时注意更新 right 和 left 的方式,保证在每次循环中 right 和 left 一定会向中间靠拢。所以如果 X 大于 L->Data , left 应该设置为 z+1 ,而不是 z 。同样,如果 X 小于 L->Data , 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)
            left = mid + 1;
      else if (X < L->Data)
            right = mid - 1;
      else
            return mid;
    }
    return NotFound;// 注意这里返回你定义的NotFound,也就是0
}


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

陶远航 发表于 2023-6-4 20:38:35

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

如果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)
            left = mid + 1;
      else if (X < L->Data)
            right = mid - 1;
      else
            return mid;
    }
    return NotFound;// 注意这里返回你定义的NotFound,也就是0
}

a905448839 发表于 2023-6-4 22:50:46

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

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

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

a905448839 发表于 2023-6-4 22:50:51

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

两位大佬的问题的确能够解决这个题,但是思路和我的有出入。我是想一直用二分法找出中间点那个是不是要找的值。如果不是一直找到左边的点和右边的点相等的情况下返回NotFound。我的原始代码基础上有什么改进的办法没有呢?
页: [1]
查看完整版本: 为什么我的代码会超时?