两种检索算法

1.问题
写出两种检索算法：在一个排好序的数组T[1…..n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0；
2.解析
本次实验采用顺序查找和二分查找
1.二分查找：
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
2.顺序查找：
从数组的第一个数开始按顺序查找，将每一个数与x相比，如果相等输出下标j，如果到结尾了还没找到，则输出j=0；
3.设计
int sequence_search(int *T,const int n,const int x){
int i;for(i = 0;iif(T[i] == x)
return i;
}
if(i == n)
return -1;
}//顺序查找

int binary_search(int *T,const int x,const int n)
{
int head,tail,mid;
tail = 0,head = n-1;
while(tail <= head){
mid = (head + tail) / 2;
if(T[mid] == x)
return mid;
else if(T[mid] < x)
tail = mid + 1;
else if(T[mid] > x)
head = mid - 1;
}
return -1;
} //二分查找

4.分析
算法复杂度
方法1：二分查找
O(logn)
方法2：顺序查找
O(n)
5.源码
https://github.com/joserfdave/arithmetic/blob/main/Traverse %26 Binary Search