为什么我的代码会超时？
二分查找本题要求实现二分查找算法。
函数接口定义：
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;
}
}
结果部分超时：
求高手给出超时原因！十分感谢！ 你的代码可能会陷入无限循环，导致超时。问题在于你的“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
}
这个修复的版本应该可以解决你的超时问题。 可能的超时原因是您的循环没有结束条件。请检查是否有以下情况：
如果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
} 陶远航 发表于 2023-6-4 20:38
可能的超时原因是您的循环没有结束条件。请检查是否有以下情况：
如果X不存在于L->Data，请确保程序可以 ...
两位大佬的问题的确能够解决这个题，但是思路和我的有出入。我是想一直用二分法找出中间点那个是不是要找的值。如果不是一直找到左边的点和右边的点相等的情况下返回NotFound。我的原始代码基础上有什么改进的办法没有呢？ isdkz 发表于 2023-6-4 20:37
你的代码可能会陷入无限循环，导致超时。问题在于你的“while”循环的终止条件不够完备。你的代码是这样设 ...
两位大佬的问题的确能够解决这个题，但是思路和我的有出入。我是想一直用二分法找出中间点那个是不是要找的值。如果不是一直找到左边的点和右边的点相等的情况下返回NotFound。我的原始代码基础上有什么改进的办法没有呢？
页:
[1]