C语言从有序递增的顺序表中查找值为x的元素

这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识，请查看：数据结构 -> 线性表

问题描述：

线性表(a₁, a₂, a₃, …, a_n)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成用最少时间在表中查找数值为x的元素，若找到将其与后继元素位置相交换，若找不到将其插入表中并使表中元素仍递增有序。

问题解答：

算法思想：顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找法。

本题代码如下：

void SearchExchangeInsert(ElemType A[], ElemType x){
    int low=0, high=n-1;  //low和high指向顺序表下界和上界的下标
    while(low<=high){
        mid = (low+high)/2;  //找中间位置
        if(A[mid]==x) break;  //找到 x，退出 while 循环
        else if (A[mid]<x) low = mid+1;  //到中点 mid 的右半部去查
        else high=mid-1;  //到中点mid的左半部去查
    } //下面两个if语句只会执行一个  
    if(A[mid] == x && mid != n-1) {  //若最后一个元素与x相等，则不存在与其后继交换的操作  
        t=A[mid]; A[mid]=A[mid+1]; A[mid+1]=t;
    }
    if(low>high) {  //查找失败，插入数据元素x
        for(i=n-1; i>high; i--) A[i+l]=A[i] ;  //后移元素
            A[i+1]=x;  //插入 x
    }  //结束插入
}

本题的算法也可以写成三个函数：查找函数、交换后继函数与插入函数。写成三个函数的优点是逻辑清晰、易读。