設計-C語言的相關問題，求助大神們。

C語言的相關問題，求助大神們。

原題如圖所示。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;
}

最佳回答：

注意數組要足夠大，不然插入新元素時下標會越界
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;
}