为什么我的代码会超时？

a905448839

二分查找

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

函数接口定义：

1. Position BinarySearch( List L, ElementType X );

复制代码

其中List结构定义如下：

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

复制代码

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

裁判测试程序样例：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAXSIZE 10
   
5. #define NotFound 0
   
6. typedef int ElementType;
   
7. 
   
8. typedef int Position;
   
9. typedef struct LNode *List;
   
10. struct LNode {
    
11.     ElementType Data[MAXSIZE];
    
12.     Position Last; /* 保存线性表中最后一个元素的位置 */
    
13. };
    
14. 
    
15. List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
    
16. Position BinarySearch( List L, ElementType X );
    
17. 
    
18. int main()
    
19. {
    
20.     List L;
    
21.     ElementType X;
    
22.     Position P;
    
23. 
    
24.     L = ReadInput();
    
25.     scanf("%d", &X);
    
26.     P = BinarySearch( L, X );
    
27.     printf("%d\n", P);
    
28. 
    
29.     return 0;
    
30. }
    
31. 
    
32. /* 你的代码将被嵌在这里 */

复制代码

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

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


我的代码：

1. Position BinarySearch( List L, ElementType X )
   
2. {
   
3.         Position right = L->Last,left = 1;
   
4.     Position z = (right+left)/2;
   
5.         while(1)
   
6.         {
   
7.         if(X > L->Data[z])
   
8.         {
   
9.             left = z;
   
10.             z = (right+left+1)/2;
    
11.         }
    
12.         else if(X < L->Data[z])
    
13.         {
    
14.             right = z;
    
15.              z = (right+left)/2;
    
16.         }
    
17.         else
    
18.             return z;
    
19.         if(right == left)
    
20.         return 0;
    
21.     }
    
22.    
    
23. }

复制代码

结果部分超时：


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

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 。

下面是修复后的代码：

1. Position BinarySearch( List L, ElementType X )
   
2. {
   
3.     Position right = L->Last, left = 1;
   
4.     while (left <= right)
   
5.     {
   
6.         Position mid = (right + left) / 2;
   
7.         if (X > L->Data[mid])
   
8.             left = mid + 1;
   
9.         else if (X < L->Data[mid])
   
10.             right = mid - 1;
    
11.         else
    
12.             return mid;
    
13.     }
    
14.     return NotFound;  // 注意这里返回你定义的NotFound，也就是0
    
15. }
    

复制代码

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

陶远航

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

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

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

下面是改进后的代码：

1. Position BinarySearch( List L, ElementType X )
   
2. {
   
3.     Position right = L->Last, left = 1;
   
4.     while (left <= right)
   
5.     {
   
6.         Position mid = (right + left) / 2;
   
7.         if (X > L->Data[mid])
   
8.             left = mid + 1;
   
9.         else if (X < L->Data[mid])
   
10.             right = mid - 1;
    
11.         else
    
12.             return mid;
    
13.     }
    
14.     return NotFound;  // 注意这里返回你定义的NotFound，也就是0
    
15. }

复制代码

a905448839

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

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

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

a905448839

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

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