数据结构：线性表查找的三种方式

只要是静态查找表即可

#define ElemType int
typedef struct {
ElemType *d;
int length;
}SSTable;

顺序查找 S(n)=O(1) 哨兵空间

int Search_Seq(SSTable t,ElemType key)
{t.d[0]=key;for (int i = t.length; i >0 ; i--) {if(t.d[i]==t.d[0]){return i;}}return 0;
}

---

折半查找（二分查找）：要求必须是顺序存储，且元素内有序

非递归

int Search_bin_notDG(SSTable t,ElemType key)
{int low=1,high=t.length-1;while (low<=high){int mid=(high+low)/2;if(t.d[mid]==key){return mid;}else if(t.d[mid]>key){high=mid-1;} else{low=mid+1;}}return 0;
}

递归

int Search_bin_DG(SSTable t,ElemType key,int high,int low)
{if(low>high){return 0;}int mid=(low+high)/2;if(t.d[mid]==key){return mid;}else if(t.d[mid]<key){Search_bin_DG(t,key,high,mid+1);}else{Search_bin_DG(t,key,mid-1,low);}}

分块查找：主要是利用索引表进行查找，块间有序，块内有无序决定块内查找方式