本文主要是介绍设计一个算法，用最少的时间在顺序表中找到x，若找到，与后继交换，找不到插入到顺序表中，任保持有序。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：线性表（a1,a2.........an）中的元素递增有序且按照顺序存储在计算机中。设计一个算法，用最少的时间在顺序表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，将其插入到顺序表中，任保持递增有序。
思想：最少时间找到，则使用折半查找进行寻找x，确定x是否在表中。查找结束后，进行交换后继或者插入。
代码：
//折半查找
int HalfSearsh(SqLlist &L,ElemType x){int mid,low=0,high=L.length-1;if(low<=higt){mid=(low+higt)/2;if(L.data[mid]==x){//查找成功 return mid;}else if (L.data[mid]<x){low = mid + 1;//右侧找 }else{higt = mid - 1;//左侧找 }}return higt;//查找失败，最后一个小于x的值的下标为hight
}
//交换
void swap(ElemType &a,ElemType &b){int temp;temp=a;a=b;b=temp
}
//插入
int Insert(SqList &L,int index,ElemType x){if(index<0 || index>L.length) {return false;}for(int i=L.length-1;i>=index;i--){L.data[i+1]=index[i];//后移动 }L.data[i+1]=x;//插入 L.length++;return true;}
void SearchExchangeInsert(SqList &L,ElemType x){int XIndex=HalfSearsh(L,x);//折半查找元素x//查找成功，与后继进行交换if(L.data[XIndex]==x){if(XIndex != L.length-1) {//x为最后一个元素时，不需要交换 swap(L.data[XIndex],L.data[XIndex+1]) ; } else{//没有找到，则在对应的位置插入x Insert(L,XIndex+1,x);}}
时间复杂度O(logn) 到 O(n) 之间，具体取决于 x 是否在列表中；空间复杂度O（1）
这篇关于设计一个算法，用最少的时间在顺序表中找到x，若找到，与后继交换，找不到插入到顺序表中，任保持有序。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
