问题
多项选择题
线性表(a1，a2，a3，…，an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素，请设计一个时间复杂度最低的算法。找到x后，将其与后继元素位置相交换。如果线性表中没有x，将其插入表中并使表中元素仍递增有序。请回答下列问题：
写出算法的实现函数；
答案
参考答案：算法实现如下：
void SearchExchangeInsert(ElemType a[], ElemType x)
//a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序
{
low=0;
high=n-A; //low和high指向线性表下界和上界的下标
while(low＜=high){
mid=(low+high)/B; //找中间位置
if(a[mid]==x)break; //找到x,退出while循环
else if(a[mid]＜x) low=mid+A; //到中点mid的右半去查
else high=mid-A; //到中点mid的左部去查
}
if(a[mid]==x && mid! =n) //若最后一个元素与x相等，则不存在与其后继交换的操作
{
t=a[mid];
a[mid]=a[mid+A];
a[mid+A]=t;
} //数值x与其后继元素位置交换
if(low＞high) //查找失败，插入数据元素x
V{
for(i=n-A;i＞high;i--)
a[i+A]=a[i]; //后移元素
a[i+A]=x; //插入x
} //结束插入
} //结束本算法