题目

编写一个函数，利用二分查找算法在一个有序表中插入一个关键字k，并保持表的有序性。

分析

先在有序表中利用二分查找算法查找关键字值等于或小于k的结点，m指向正好等于k的结点或l指向关键字正好大于k的结点，然后采用移动法插入k结点即可。

本题的难点就是如何利用二分查找算法找到合适的插入位置。

有两种情况：第一种是有序表中没有等于关键字k的结点，寻找大于k的结点即可；第二种是有序表中存在等于关键字k的结点，寻找等于k的结点即可。

图解如下：

将两种情况用同一部分代码来处理，定义一个标志位变量flag，用来记录是否有等于关键字k的情况，初始为0表示没有等于关键字k的情况，如果有则将flag置为1，然后退出循环，最终根据标志位flag来判断插入位置。

代码

核心代码：

/* 使用二分查找在顺序表中插入元素k */ 
void insertK(int nums[],int n,int k){
	int mid;// 记录中间下标 
	int low=0,high=n-1;
	int flag=0;// 标志，用来记录是否有等于k的值 
	int pos;// 定义的变量，为插入的位置 
	while(low<=high&&flag==0){// 循环当low>high时跳出循环 
		mid=(low+high)/2;
		if(nums[mid]==k){
			flag=1;// 如果发现有关键字等于k,则将标志flag置为1，退出循环然后插入k 
		}else if(nums[mid]>k){
			high=mid-1;
		}else if(nums[mid]<k){
			low=mid+1;
		}
	}
	/* 确定插入位置 */ 
	if(flag==1){// 如果flag为1则发现序列中有关键字等于k，则使插入位置等于mid
		pos=mid; 
	}else{// 如果flag为0则表示序列中没有与关键字k相等的值，则插入位置为low 
		pos=low;
	}
	/* 插入关键字k */
	for(int i=n-1;i>=pos;i--){
		nums[i+1]=nums[i];
	} 
	nums[pos]=k;
}

完整代码如下：

#include<stdio.h>

/* 打印数组 */ 
void printArr(int nums[],int n){
	printf("\n");
	for(int i=0;i<n;i++){
		printf("%d\t",nums[i]);
	}
	printf("\n");
}

/* 使用二分查找在顺序表中插入元素k */ 
void insertK(int nums[],int n,int k){
	int mid;// 记录中间下标 
	int low=0,high=n-1;
	int flag=0;// 标志，用来记录是否有等于k的值 
	int pos;// 定义的变量，为插入的位置 
	while(low<=high&&flag==0){// 循环当low>high时跳出循环 
		mid=(low+high)/2;
		if(nums[mid]==k){
			flag=1;// 如果发现有关键字等于k,则将标志flag置为1，退出循环然后插入k 
		}else if(nums[mid]>k){
			high=mid-1;
		}else if(nums[mid]<k){
			low=mid+1;
		}
	}
	/* 确定插入位置 */ 
	if(flag==1){// 如果flag为1则发现序列中有关键字等于k，则使插入位置等于mid
		pos=mid; 
	}else{// 如果flag为0则表示序列中没有与关键字k相等的值，则插入位置为low 
		pos=low;
	}
	/* 插入关键字k */
	for(int i=n-1;i>=pos;i--){
		nums[i+1]=nums[i];
	} 
	nums[pos]=k;
}

int main(){
	int nums[]={1,2,3,4,5,6,7};
	int n=7;
	int k=5;
	insertK(nums,n,k);// 插入k
	printArr(nums,n);// 打印数组 
	
	return 0;
}

运行结果：