在有序线性表中查找x元素

问题描述：线性表(a1, a2, ..., an)中元素递增有序且按顺序存储于计算机内。要求设计以算法完成用最少时间在表中查找数值为x的元素，若找到将其与后继元素位置相交换，若找不到将其插入表中并使表中元素仍递增有序。 

分析：顺序存储的线性表递增有序，结合题目要求，故可以使用折半查找法（时间复杂度为log2n（以2为底，n的对数））。

void serachExchangeInsert(int *a, int &n, int x)
{
int left, right, mid;
left = 0, right = n-1;
while(left <= right)
    //二分查找
{
mid = (left + right) / 2;
if(a[mid] == x) break;
else if(a[mid] < x) left = mid + 1;
else right = mid - 1;
}
if(a[mid] == x && mid != n-1)
//与后继元素交换
{
int t = a[mid];
a[mid] = a[mid+1];
a[mid+1] = t;
}
else
//查找失败，插入x
{
for(int i = n-1; i > right; --i)//二分查找，若没有找到x，a[right]<x, a[left]>x，故x要插入到right的后面
a[i+1] = a[i];
a[right+1] = x;
//插入x
n++;
//插入了一个新元素，表长+1
}
} 

最后

以上就是文艺巨人为你收集整理的在有序线性表中查找x元素的全部内容，希望文章能够帮你解决在有序线性表中查找x元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。