线性表(a1,a2,...,an)中元素递增有序且按顺序存储

//使用折半查找法
void SearchExchangeInsert(ElemType A[]，ElemType x)
{
	int low = 0,high = n-1, mid;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(A[mid] == x) 
			break;
		else if (A[mid] < x)
			low = mid + 1;
		else 
			high = mid - 1;
	}
	if (A[mid] == X && mid != n-1)
	{
		t = A[mid];
		A[mid] = A[mid + 1];
		A[mid + 1] = t;
	}

	if (low > high)
	{
		for (int i = n-1; i > high; i--)
			A[i + 1] = A[i];
		A[i + 1] = x;
		
	}
}

顺序存储的线性表递增有序，可以顺序查找也可以折半查找，题目要求“最少时间查找值为x的元素”，选用折半查找                                        

算法如下：

#define status int
#define true 1
#define false 0
status SearchExchangeInsert(ElemType a[],int *n,ElemType x)
{
 int low=0,high=*n-1,mid,i;
 status s=false;
 //数组长度检查                           
 if(low>high) return s;
 if(*n<=0) return s;
 //折半查找                               
 while(low<=high)
 {
 mid=(low+high)/2;
 if(a[mid]==x)
 {
 break;
 }
 else if(a[mid]<x)
 {
 low=mid+1;
 }
 else
 {
 high=mid-1;
 }
 }
 //查找成功                               
 if(low<=high)
 {
 //是否最后一个元素 
 s=true;
 if(mid==*n-1) return s;
 //不是最后一个元素，则与后继交换
 a[mid]=a[mid+1];
 a[mid+1]=x;
 }
 else //查找失败                         
 {
 for(i=*n-1;i>=low;i--)
 a[i+1]=a[i];
 a[low]=x;
 (*n)++;
 }
 return s;
}