4-10 二分查找

4-10 二分查找

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

函数接口定义：

Position BinarySearch( List Tbl, ElementType K );

其中List结构定义如下：

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

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

 

输入样例1：

5 12 31 55 89 101 31

输出样例1：

2

输入样例2：

3 26 78 233 31

输出样例2：

0代码： 1 #include<iostream> 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 using namespace std; 6 #define MAXSIZE 10 7 #define NotFound 0 8 typedef int ElementType; 9 10 typedef int Position; 11 typedef struct LNode *List; 12 struct LNode { 13 ElementType Data[MAXSIZE]; 14 int Last; /* 保存线性表中最后一个元素的位置 */ 15 }; 16 17 List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */ 18 Position BinarySearch( List Tbl, ElementType K ); 19 20 int main() 21 { 22 List Tbl; 23 ElementType K; 24 Position P; 25 Tbl = ReadInput(); 26 scanf("%d", &K); 27 P = BinarySearch( Tbl, K ); 28 printf("%d\n", P); 29 30 return 0; 31 } 32 List ReadInput() 33 { 34 int num; 35 List L=(List)malloc(sizeof(LNode)); 36 L->Last=1; 37 cin>>num; 38 for(int i=1;i<=num;i++) 39 { 40 cin>>L->Data[i]; 41 L->Last=L->Last+1; 42 } 43 return L; 44 } 45 46 int BinarySearch( List Tbl, ElementType K) 47 { 48 int right=Tbl->Last,left=1,mid; 49 if(Tbl==NULL) return 0; 50 else { 51 while(left<=right) 52 { 53 mid=(left+right)/2; 54 if(K==Tbl->Data[mid]) 55 { 56 return mid; 57 } 58 else if(K<Tbl->Data[mid]) 59 { 60 right=mid-1; 61 } 62 else{ 63 left=mid+1; 64 } 65 } 66 } 67 return NotFound; 68 }