本题要求实现二分查找算法.
函数接口定义:
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
- #include
- #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 )
- {
- int left=1,right=L->Last;// 设置左右指针
- int mid;
- while(left<=right){
- // 左右指针相遇时, 循环跳出
- mid=(left+right)/2;
- if(L->Data[mid]<X)
- left=mid+1;
- else if(L->Data[mid]==X)
- return mid;
- else right=mid-1;
- }
- return NotFound; // 若未找到, 返回 NotFound
- }
注意:
二分查找仅用于有序序列
来源: http://www.bubuko.com/infodetail-3145202.html