C语言的相关问题，求助大神们。

Question

原题如图所示。C语言中，设计函数：search()，用折半查找法在已排序的n个数种查找指定的数据，若存在，返回其所处的位置，否则，将其插入适当位置使数据仍有序。
这个程序我已经写完了前半段，但是后半段的那个插入其中使其保持原来的顺序，我的是从大到小排列，不知道后半段代码该如何写了。求助大神们。
int search (int *d,int n,int key){
int low,high,mid,i;
low=0;
high=n-1;
while( low <= high){
mid=(low+high)/2;
if(key==d[mid]) return mid;
else if(key>d[mid]) high=mid-1;
else low = mid + 1;
}
return 0;
}

Answer 1

注意数组要足够大，不然插入新元素时下标会越界
int Search(int *d, int n, int key) {
int low, high, mid;
low = 0;
high = n-1;
while( low <= high){
mid = (low + high) / 2;
if(key == d[mid])
return mid;
else if(key > d[mid])
high = mid - 1;
else low = mid + 1;
if((low == mid || high == mid) && d[mid] != key) {
if(d[mid] > key) {
for(int i = n ; i > mid + 1; i--)
d[i] = d[i - 1];
d[mid + 1] = key;
return 666;
} else {
for(int i = n; i > mid; i--)
d[i] = d[i - 1];
d[mid] = key;
return 666;
}
}
}
return 0;
}