本文共 1801 字，大约阅读时间需要 6 分钟。

题目：线性表（a1,a2,a3,…,an）中元素递增有序且按顺序存储在计算机中。要求设计一个算法完成用最少时间在表中查找值为x的元素，若找到将其与后继元素位置相交换，若找不到将其插入表中并使表中元素仍递增有序。

算法思想：有序顺序表，可以用二分查找（折半查找）。

int BinarySearch(ElemType A[], ElemType x){	int low = 0, high = n-1, mid; //low记录最左边元素位置，high记录最右边元置，mid记录中间位置	while(low<=high){		mid = (low+high)/2; //mid记录最中间位置（不为整数时，记录前面的那个位置） 		if(L.data[mid] < x) 			low = mid+1; // 中间元素小于x，x在后半部分，low设置为mid下一个位置 		else if (L.data[mid] > x) 			high = mid-1; //x在前半部分，high设置为mid前一个元素的位置 		else 			return mid; // mid位置的值等于x，返回这个位置（下标，一个数字） 	} 	return -1; //查不到x，返回-1表示错误

解析：

1. 设置三个变量，low和high指定顺序表的第一个元素和最后一个元素的下标。mid为中间位置。
2. while循环的出口条件是low>high，比如查找20这个元素，随着while的执行，high变小，low变大，查不到元素最终会返回-1。
3. 最后有查找元素13和20的例子。
4. 程序会返回x所在的位置或者查找失败。

主函数调用BinarySearch()函数

void SearchExchangeInsert(ElemType A[], ElemType x){	int res;	res = BinarySearch(SqList &L, ElemType x);	if(res != -1 && res!= n-1){		temp=A[res]; A[res]=A[res+1]; A[res+1]=temp;	} 	if(res == -1) //二分查找只是返回错误信息，没有找到具体x应该插入的位置 	{		for(i=n-1; A[i]>x; i--) A[i+1] = A[i]; //从最后一位开始，大于x的元素依次右移一位		A[i+1] = x; 	}}

解析：

1. 将数组A和x作为参数传递给SearchExchangeInsert()函数，BinarySearch()函数查找x所在位置或者返回查找失败信息。
2. 如果 查找成功且不是最后一个元素，执行位置交换操作，注意使用中间变量。
3. 如果x在顺序表末尾，不能和它后继元素位置互换，忽略掉就行。
4. 如果查找失败，需要将x插入到数组中的位置，使数组依然是有序线性表。使用for循环，从最后一个一个元素开始，将大于x的元素依次右移一位。
5. 最后一次for循环，i位置的元素小于x，原来i+1位置（现在右移到i+2位置的）元素大于x。将x放在现在i+1的位置。最后将x插入表中。

查找13：

else if (L.data[mid] > x) 			high = mid-1; //x在前半部分，high设置为mid前一个元素的位置

重新设置上界high，删除了后半部分 

if(L.data[mid] < x) 			low = mid+1; // 中间元素小于x，x在后半部分，low设置为mid下一个位置

重新设置下界low

满足mid=x，返回mid。

查找20：

此时依然满足L.data[mid] > x，接着执行 high = mid-1; high<low， 退出了while循环，返回-1。

转载地址：http://seeii.baihongyu.com/