二分查找-白红宇

二分查找

阅读量：3936 次

发布时间：2019-05-23

本文共 1755 字，大约阅读时间需要 5 分钟。

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

函数接口定义：

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 0typedef 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：

12 31 55 89 101

输出样例1：

输入样例2：

26 78 233

输出样例2：

觉得很简单的一个题，自己写，有一个数据超时，说明死循环

Position BinarySearch( List L, ElementType X ){//函数BinarySearch要查找X在Data中的位置//即数组下标（注意：元素从下标1开始存储）	if(L->Last==0) return NotFound;	int mid;	int left,right;	left=1;	right=L->Last;	int flag=0;	while(1)	{		mid=(left+right)/2;		if(L->Data[mid]==X) return mid;		if(L->Data[mid]
   
    Last) return NotFound；		mid=(right+left)/2;	}}

将if(mid==1||mid==L->Last) return NotFound；

改为if(right<left) return NotFound；就对了

分析，比如 3 8 10 12 15 17

要查找的是11，则最后有left=right=4,（下标为4对应着12），12>11，则right=mid-1,为3，结束条件无用。

最终代码

Position BinarySearch( List L, ElementType X ){//函数BinarySearch要查找X在Data中的位置//即数组下标（注意：元素从下标1开始存储）	if(L->Last==0) return NotFound;	int mid;	int left,right;	left=1;	right=L->Last;	int flag=0;	while(left<=right)	{		mid=(left+right)/2;		if(L->Data[mid]==X) return mid;		if(L->Data[mid]

转载地址：http://klkwi.baihongyu.com/

你可能感兴趣的文章