顺序查找
算法描述
顺序比较即可。
平均查找长度
(n+1)/2, 其中n为表长。
时间复杂度
O(n)
#include "stdio.h" typedef struct student{ int id; /*学生编号*/ char name[10]; /*学生姓名*/ float score; /*成绩*/ }Student; int search(Student stu[],int n,int key){ int i; for(i=0; i<n; i++) if( stu[i].id == key ) /*查找成功*/ return i; return -1; /*查找失败*/ } void main() { Student stu[4] = {{1004,"TOM",100} , {1002,"LILY",95}, {1001,"ANN",93}, {1003,"LUCY",98} }; /*初始化结构体数组*/ int addr; /*要查找的记录的地址*/ addr = search(stu,4,1003); printf("Student ID: %d ",stu[addr].id); /*输出查找到的记录的信息*/ printf("Student name: %s ",stu[addr].name); printf("Student score: %f ",stu[addr].score); }
折半查找
算法描述
限制：待查表必须是有序的向量(在内存中连续存储)
首先和数组中点比较，如果等于则返回，如果小于中点则在左边区间查找，如果大于中点则在右边区间查找。
平均查找长度
lg(n+1)
#include "stdio.h" bin_search(int A[],int n,int key){ int low,high,mid; low = 0; high = n-1;//因为从0开始，所以减1 while(low<=high) { mid = (low + high)/2;//从中间开始找，先找出中间的数为多少 if(A[mid]==key)return mid; /*查找成功，返回mid*/ if(A[mid]<key){ low = mid + 1; /*在后半序列中查找*/ } if(A[mid]>key){ high = mid - 1; /*在前半序列中查找*/ } } return -1; /*查找失败，返回-1*/ } main() { int A[10] = {2,3,5,7,8,10,12,15,19,21},i,n ,addr; printf("The contents of the Array A[10] are "); for(i=0;i<10;i++) printf("%d ",A[i]); /*显示数组A中的内容*/ printf(" Please input a interger for search "); scanf("%d",&n); /*输入待查找的元素*/ addr = bin_search(A,10,n); /*折半查找，返回该元素在数组中的下标*/ if(-1 != addr) /*查找成功*/ printf("%d is at the %dth unit is array A ",n,addr); else printf("There is no %d in array A ",n); /*查找失败*/ }