#include <stdio.h> /** * 用折半法尝试查找要插入的值,如果查找到,就返回该值的下一个元素的下标,如果没找到,可以返回low所在位置的下标 * * @param arr 原来的数组 * @param len 数组的长度 * @param key 需要插入的数值 * * @return 返回插入的地址 */ int sortInsert(int arr[],int len,int key){
int low=0,high=len,mid;
int flag = 1;
while (flag) {
if (low <= high) {
mid = (low + high)/2;
if (key == arr[mid]) {
flag = 0;
//查找到后插入相同值的后面 return mid+1;
}else if (key > arr[mid]){
low = mid + 1; }else{
high = mid -1; }
}else{
flag = 0;
}
} //没查找到时可以插入low的位置 return low; }
int main(int argc, const char * argv[]) {
int a[11]={1,4,6,13,16,18,25,37,48,65};
int len = sizeof(a)/sizeof(int);
int key;
int loc;
printf("请输入要插入的数:");
scanf("%d",&key);
loc=sortInsert(a,len,key);
//将所有loc后面的元素往后移动一位 for (int i = len; i > loc; i--) {
a = a[i-1];
}
//将要插入的元素放入loc位置中 a[loc] = key;
//遍历所有元素输出 for (int i = 0; i < len; i++) {
printf("%d ",a);
} //printf("%d\n",loc);
return 0; }
|